Write a function to generate all permutations of a given string in such a way that each permutation is generated only once, even if there are duplicate characters in the string. ### Constraints: - The length of the string is between 1 and 9 inclusive. ### Examples: 1. Input: 'aabc' Output: ['aabc', 'aacb', 'abac', 'abca', 'acab', 'acba', 'baac', 'baca', 'bcaa', 'caba', 'cbaa'] 2. Input: 'xyz' Output: ['xyz', 'xzy', 'yxz', 'yzx', 'zxy', 'zyx']

``` def generate_permutations(s): from collections import Counter results = [] def backtrack(path, counter): if len(path) == len(s): results.append(''.join(path)) return for char in counter: if counter[char] > 0: path.append(char) counter[char] -= 1 backtrack(path, counter) path.pop() counter[char] += 1 backtrack([], Counter(s)) return sorted(results) # Example usages: print(generate_permutations('aabc')) # ['aabc', 'aacb', 'abac', 'abca', 'acab', 'acba', 'baac', 'baca', 'bcaa', 'caba', 'cbaa'] print(generate_permutations('xyz')) # ['xyz', 'xzy', 'yxz', 'yzx', 'zxy', 'zyx'] ```