Day 1 - Permutations of a String.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving	Strings Recursion Backtracking

🚀 Day 1. Permutations of a String 🧠

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

💡 Problem Description:

You are given a string s, which may contain duplicate characters. Your task is to generate and return an array of all unique permutations of the string. You can return the permutations in any order.

🔍 Example Walkthrough:

Example 1

Input:
s = "ABC"
Output:
["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
Explanation:
Given string ABC has 6 unique permutations.

Example 2

Input:
s = "ABSG"
Output:
["ABGS", "ABSG", "AGBS", "AGSB", "ASBG", "ASGB", "BAGS", "BASG", "BGAS", "BGSA", "BSAG", "BSGA", "GABS", "GASB", "GBAS", "GBSA", "GSAB", "GSBA", "SABG", "SAGB", "SBAG", "SBGA", "SGAB", "SGBA"]
Explanation:
Given string ABSG has 24 unique permutations.

Example 3

Input:
s = "AAA"
Output:
["AAA"]
Explanation:
No other unique permutations can be formed as all the characters are the same.

Constraints

• 1 <= s.size() <= 9
• s contains only uppercase English alphabets.

🎯 My Approach:

1. Lexicographical Permutation Method:

   • Sort the characters of the string to generate permutations in lexicographical order.
   • Use a loop to find the next lexicographical permutation until all permutations are found.

2. DFS with Backtracking:

   • Use backtracking to generate all permutations.
   • Avoid duplicates by skipping over elements that are the same and ensuring a sorted order before starting.

3. Key Steps:

   • Sort the string or array of characters to start with the smallest permutation.
   • Generate all permutations using a DFS approach or iterate through lexicographical order using the next_permutation() function.
   • Ensure uniqueness by checking and avoiding duplicate entries in the result.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N! * N), where N is the length of the string. Generating all permutations takes O(N!), and sorting or creating permutations takes O(N).
• Expected Auxiliary Space Complexity: O(N), for storing intermediate permutations in recursion or iteration.

📝 Solution Code

Approach : Using STL next_permutation()

Code (C++)

class Solution {
public:
    vector<string> findPermutation(string s) {
        vector<string> res;
        sort(s.begin(), s.end());
        do {
            res.push_back(s);
        } while (next_permutation(s.begin(), s.end()));
        return res;
    }
};

👨‍💻 Alternative Approaches

Approach 2: Using DFS with Backtracking

• Expected Time Complexity: O(N! * N), where N is the length of the string. Backtracking generates all unique permutations.
• Expected Auxiliary Space Complexity: O(N), for recursion stack and used flags.

Approach 2: DFS with Backtracking

Code (C++)

class Solution {
public:
    void dfs(string &s, vector<bool> &used, string &curr, vector<string> &res) {
        if (curr.size() == s.size()) {
            res.push_back(curr);
            return;
        }
        for (int i = 0; i < s.size(); i++) {
            // Skip used characters or duplicates
            if (used[i] || (i > 0 && s[i] == s[i - 1] && !used[i - 1])) continue;
            used[i] = true;
            curr += s[i];
            dfs(s, used, curr, res); // Recursive call
            used[i] = false; // Backtrack
            curr.pop_back();
        }
    }

    vector<string> findPermutation(string s) {
        vector<string> res;
        sort(s.begin(), s.end()); // Step 1: Sort to handle duplicates
        vector<bool> used(s.size(), false);
        string curr;
        dfs(s, used, curr, res); // Start backtracking
        return res;
    }
};

Code (Python)

from itertools import permutations

class Solution:
    def findPermutation(self, s):
        return sorted(set(["".join(p) for p in permutations(s)]))  # Unique permutations

Code (Java)

class Solution {
    public ArrayList<String> findPermutation(String s) {
        ArrayList<String> res = new ArrayList<>();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        do res.add(new String(chars));
        while (next(chars));
        return res;
    }

    private boolean next(char[] c) {
        int i = c.length - 2, j = c.length - 1;
        while (i >= 0 && c[i] >= c[i + 1]) i--;
        if (i < 0) return false;
        while (c[j] <= c[i]) j--;
        char t = c[i]; c[i] = c[j]; c[j] = t;
        for (int l = i + 1, r = c.length - 1; l < r; l++, r--) {
            t = c[l]; c[l] = c[r]; c[r] = t;
        }
        return true;
    }
}

Code (Python)

class Solution:
    def findPermutation(self, s):
        s, res = ''.join(sorted(s)), []
        while s:
            res.append(s)
            s = self.next(s)
        return res

    def next(self, s):
        s = list(s)
        i = len(s) - 2
        while i >= 0 and s[i] >= s[i + 1]: i -= 1
        if i < 0: return None
        j = len(s) - 1
        while s[j] <= s[i]: j -= 1
        s[i], s[j] = s[j], s[i]
        return ''.join(s[:i + 1] + s[i + 1:][::-1])

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count