public class Solution {
    public ArrayList<String> Permutation(String str) {
       if(str == null){
           return null;
       }
        ArrayList<String> result = new ArrayList<>();
        permutationHelper(str.toCharArray(),0,result);
        Collections.sort(result);
        return result;
    }
        public void permutationHelper(char[] chars, int start, ArrayList<String> result){
        if(start==chars.length -1 ){
            result.add(String.valueOf(chars));
            return;
        }
        Set<Character> charSet = new HashSet<>();
        for (int i = start;i<chars.length;i++){

            if(!charSet.contains(chars[i])) {
                charSet.add(chars[i]);
                char temp = chars[i];
                chars[i] = chars[start];
                chars[start] = temp;
                //i + 1后的全排列
                permutationHelper(chars, start + 1, result);
                char temp2 = chars[i];
                chars[i] = chars[start];
                chars[start] = temp2;
            }
        }
    }
}