String Permutations

# String Permutations ## Difficulty Medium ## Tags `string`, `recursion`, `backtracking` ## Problem Statement Given a string `s`, return all possible permutations of its characters. If the string contains duplicate characters, the output should contain only unique permutations. ## Constraints - 1 ≤ s.length ≤ 8 - `s` consists of lowercase English letters. - Return the permutations in any order. ## Signatures ### Python ```python def get_permutations(s: str) -> List[str]: pass ``` ### Java ```java public class Solution { public List<String> get_permutations(String s) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<string> get_permutations(string s) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<string> get_permutations(string s) { } }; ``` ### C ```c vector<char*> get_permutations(char* s) { } ``` ### Ruby ```ruby def get_permutations(s) end ``` ### Perl ```perl sub get_permutations { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def get_permutations(s: String): List[String] = { } } ``` ### Haskell ```haskell get_permutations :: ... -> ... get_permutations args = undefined ``` ### Clojure ```clojure (defn get_permutations [s] ) ``` ### Scheme ```scheme (define (get_permutations s) ) ``` ## Examples ### Example 1 **Input:** ``` s = "abc" ``` **Output:** ``` ["abc", "acb", "bac", "bca", "cab", "cba"] ``` **Explanation:** All 3! = 6 permutations of three distinct characters. ### Example 2 **Input:** ``` s = "aab" ``` **Output:** ``` ["aab", "aba", "baa"] ``` **Explanation:** Only 3 unique permutations due to duplicate 'a'. ### Example 3 **Input:** ``` s = "a" ``` **Output:** ``` ["a"] ``` ## Hints 1. Use backtracking to generate all arrangements. 2. For each position, try placing each unused character. 3. To handle duplicates: sort the string first, and skip placing a character if it's the same as the previous one and the previous one hasn't been used yet. 4. Alternatively, use a set to track which characters have been used at each level.