Untitled — Python Coding — Nerchuko Academy

String Permutations

MEDIUM

Implement a function that generates all distinct permutations of a given string. The function should return a list of these permutations. If the input string contains duplicate characters, the permutations should be unique.

Examples:

Example 1:

Input: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"] (Order doesn't matter)

Example 2:

Input: s = "aab"
Output: ["aab", "aba", "baa"] (Unique permutations only)

Example 3:

Input: s = "a"
Output: ["a"]

Constraints:

1 <= s.length <= 8 (String length is usually small for permutation problems due to N! complexity).
s contains lowercase English letters.

Function Signature (Python):

from typing import List

class Solution:
    def permuteString(self, s: str) -> List[str]:
        # Your code here
        pass

Solution Explanation & Interview Strategy

The Goal: We want to find all possible re-arrangements (permutations) of the characters in a given string.

For "ab", the permutations are "ab" and "ba".
For "abc", they are "abc", "acb", "bac", "bca", "cab", "cba".

If the string has repeated characters, like "aab", we only want unique permutations: "aab", "aba", "baa".

Approach 1: Recursive Backtracking (Optimal for Algorithmic Understanding)

This is the standard way to implement permutations from scratch. The core idea is to build permutations step by step. For each position in the permutation, we try placing each available character, then recursively build the rest of the permutation.
To handle duplicates in the input string effectively (and avoid generating duplicate permutations in the process), we can count character frequencies or use a technique that ensures each character is chosen only as many times as it appears.

from typing import List
from collections import Counter # Useful for handling duplicates

class Solution:
    def permuteString_recursive(self, s: str) -> List[str]:
        results = []
        char_counts = Counter(s) # Count frequency of each character
        n = len(s)

        def backtrack(current_permutation_list: List[str]):
            if len(current_permutation_list) == n:
                results.append("".join(current_permutation_list))
                return

            # Iterate through unique characters available (from char_counts keys)
            for char in char_counts:
                if char_counts[char] > 0: # If this character is still available
                    # Choose
                    current_permutation_list.append(char)
                    char_counts[char] -= 1
                    
                    # Explore
                    backtrack(current_permutation_list)
                    
                    # Unchoose (backtrack)
                    char_counts[char] += 1
                    current_permutation_list.pop()

        backtrack([])
        return results

# Example Usage:
# sol = Solution()
# print(sol.permuteString_recursive("aab")) # Output: ['aab', 'aba', 'baa']
# print(sol.permuteString_recursive("abc")) # Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

How it works (for `s = "ab"`):

char_counts = {'a': 1, 'b': 1}, n = 2. Call backtrack([]).
backtrack([]):
- Loop char = 'a': counts['a'] > 0.
  - Append 'a'. perm = ['a']. counts['a'] = 0.
  - Call backtrack(['a']):
    - Loop char = 'a': counts['a'] == 0. Skip.
    - Loop char = 'b': counts['b'] > 0.
      - Append 'b'. perm = ['a', 'b']. counts['b'] = 0.
      - Call backtrack(['a', 'b']):
        
        len(['a','b']) == 2. Add "ab" to results. Return.
      - Backtrack: counts['b'] = 1. Pop 'b'. perm = ['a'].
  - Backtrack: counts['a'] = 1. Pop 'a'. perm = [].
- Loop char = 'b': counts['b'] > 0.
  - Append 'b'. perm = ['b']. counts['b'] = 0.
  - Call backtrack(['b']): (similar steps lead to adding "ba")
  - Backtrack: counts['b'] = 1. Pop 'b'. perm = [].
Return results.

Complexity Analysis:

Time Complexity: Roughly O(N * N!), where N is the length of the string. There are N! permutations. For each permutation, it takes O(N) to construct the string from the list and potentially to iterate through characters in the backtrack step (though using Counter keys is better). The number of recursive calls is related to N! nodes in the decision tree. If there are many duplicates, the number of unique permutations is N! / (k1! * k2! * ...), but the exploration might still visit many paths that lead to the same result if not pruned effectively by the counts. The Counter approach handles duplicates well.

Space Complexity: O(N) for the recursion call stack depth (maximum depth of N) and O(N) for storing the current_permutation_list. The results list will store N! permutations, each of length N, so O(N * N!) for the output. Auxiliary space excluding output is O(N).

Approach 2: Using `itertools.permutations` (Pythonic Built-in)

Python's itertools module provides a highly optimized permutations function. While interviewers usually want to see the manual recursive implementation, it's good to be aware of this for practical use and as a comparison.

from typing import List
import itertools

class Solution:
    def permuteString_itertools(self, s: str) -> List[str]:
        # itertools.permutations generates tuples of characters
        perms_tuples = itertools.permutations(s)
        
        # Convert tuples to strings and store in a set to handle duplicates from input string
        # e.g., if s = "aab", permutations of indices might lead to same char sequence
        unique_perms_strings = set()
        for p_tuple in perms_tuples:
            unique_perms_strings.add("".join(p_tuple))
            
        return list(unique_perms_strings)

# Example Usage:
# sol = Solution()
# print(sol.permuteString_itertools("aab")) 
# Output: ['aba', 'aab', 'baa'] (order may vary due to set)

Complexity Analysis (`itertools.permutations`):

Time Complexity: The itertools.permutations function itself is highly optimized. Generating all N! permutations takes O(N!) time. Joining each tuple of N characters to a string takes O(N). So, roughly O(N * N!). Adding to a set also takes time.

Space Complexity: O(N * N!) to store all the resulting string permutations in the worst case (if all characters are unique). The iterator itself is space-efficient.

Key Takeaways for Interviews:

Recursive Backtracking is Key: This is what interviewers want to see you implement manually. Clearly explain the "choose, explore, unchoose" pattern.
Base Case: The recursion stops when the current permutation's length equals the original string's length.
Handling Duplicates in Input:
- The Counter approach (as shown in Approach 1) is effective for ensuring each character is used appropriately, thus naturally producing unique permutations.
- Alternatively, if swapping elements in a list representation of the string, you'd sort the input first and then, in the recursive calls, skip using a character if it's the same as the previous character and the previous character hasn't been used in the current swap iteration. This is more complex to get right.
Complexity: Be aware of the N! nature of permutations. This limits the practical input size.
Mention `itertools`: After providing a manual solution, it's good to show you know about Python's powerful itertools.permutations for real-world scenarios.