06. String Permutations

The problem can be found at the following link: Question Link

My Approach

To find all the permutations of a given string s, we can use a backtracking approach.

• The idea is to swap characters at different positions and recursively generate all possible permutations.

• We start with the first character s[0] and swap it with every other character in the string. Then, we recursively find all permutations of the remaining characters.

• After generating all permutations, we sort the result vector to ensure the output is in lexicographically sorted order.

Time and Auxiliary Space Complexity

• Time Complexity: O(N!), where N is the length of the input string s. This is because there are N! permutations possible for a string of length N.

• Auxiliary Space Complexity: O(N!) because the out array will store all the permutations,

Code (C++)

class Solution{
public:
    vector<string> out;

    void check(string &s, int i, int &n){
        if(i == n){
            out.push_back(s);
            return; 
        }
        
        for(int j = i; j < n; ++j){
            swap(s[i], s[j]);
            check(s, i+1, n); 
            swap(s[i], s[j]); 
        }
    }
  
    vector<string> permutation(string s){
        int n = s.size(); 
        check(s, 0, n); 
        sort(out.begin(), out.end());
        return out; 
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.