Permutation of a String

When dealing with permutations of a string, one common issue arises: duplicates. For example, with input like "AAB", the total number of permutations would be 6 (3!), but many of them would be repeated. We aim to generate all unique permutations in lexicographical order to solve this.

🧠 Problem Statement

Given a string S, print all unique permutations of the characters of the string in lexicographically sorted order.

Input: ABC
Output: ABC ACB BAC BCA CAB CBA

💡 Approach

1. Backtracking: We’ll generate all permutations using backtracking.

2. Set for Uniqueness: To avoid duplicate entries, we’ll use a set<string> that automatically maintains order and uniqueness.

3. Lexicographical Order: The set helps ensure the results are sorted.

✅ Code Implementation

include <bits/stdc++.h>
using namespace std;

string swapi(int left, int i, string s) {
    swap(s[left], s[i]);
    return s;
}

void permutation(string s, int left, int right, set<string>& st) {
    // Base case: if we've fixed all characters
    if (left == right) {
        st.insert(s);
        return;
    }

    for (int i = left; i <= right; i++) {
        // Swap current index with the left index
        s = swapi(left, i, s);

        // Recur for the rest of the string
        permutation(s, left + 1, right, st);

        // Undo the swap (backtrack)
        s = swapi(left, i, s);
    }
}

vector<string> find_permutation(string s) {
    set<string> st;
    permutation(s, 0, s.size() - 1, st);

    // Transfer set elements to a vector
    return vector<string>(st.begin(), st.end());
}

🧪 Example Run

int main() {
    string input = "ABC";
    vector<string> result = find_permutation(input);

    for (const auto& str : result) {
        cout << str << " ";
    }
    return 0;
}

Output:

ABC ACB BAC BCA CAB CBA

🔍 Time Complexity

• The total number of unique permutations can go up to O(n!), where n is the length of the string.

• Using a set ensures duplicates are filtered and maintains order with O(log n) insertion per entry.

📌 Key Takeaways

• Using a set ensures both uniqueness and sorting.

• Backtracking is a powerful technique for generating permutations.

• This solution handles strings with repeating characters seamlessly.

🧪 Practice Time!

Now that you’ve seen the logic and code, it’s your turn to implement and explore!

🧤 Try this on GFG:

🔗 Permutations of a Given String - Practice Problem