class Solution {
    List<String> res = new ArrayList<>();
    boolean[] vis;

    public String[] permutation(String s) {
        vis = new boolean[s.length()];
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        backtrack(ch, new StringBuilder());
        return res.toArray(String[]::new);
    }

    void backtrack(char[] ch, StringBuilder path){
        if(path.length() == ch.length){
            res.add(path.toString());
            return;
        }

        for(int i = 0; i < ch.length; i++){
            if(i > 0 && ch[i] == ch[i - 1] && !vis[i - 1]) continue;
            if(vis[i]) continue;
            vis[i] = true;
            path.append(ch[i]);
            backtrack(ch, path);
            path.deleteCharAt(path.length() - 1);
            vis[i] = false;
        }
    }
}

class Solution {
    List<String> res = new ArrayList<>();
    boolean[] vis;

    public String[] permutation(String s) {
        vis = new boolean[s.length()];
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        backtrack(ch, 0, "");
        return res.toArray(String[]::new);
    }

    void backtrack(char[] ch, int ind, String path){
        if(ind == ch.length){
            res.add(path);
            return;
        }

        HashSet<Character> set = new HashSet<>();
        for(int i = 0; i < ch.length; i++){
            if(vis[i] || set.contains(ch[i])) continue;
            set.add(ch[i]);
            // if(i > 0 && ch[i] == ch[i - 1] && !vis[i - 1]) continue;
            vis[i] = true;
            backtrack(ch, ind + 1, path + ch[i]);
            vis[i] = false;
        }
    }
}

class Solution {
    List<String> res = new ArrayList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[0]);
    }

    void dfs(int x){
        if(x == c.length - 1){
            res.add(new String(c));
            return;
        }

        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++){
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }

    void swap(int i, int x){
        char tmp = c[i];
        c[i] = c[x];
        c[x] = tmp;
    }
}