You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Example 1:

Input: "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: "AAABBC"
Output: 188

Note:

1 <= tiles.length <= 7
tiles consists of uppercase English letters.

使用递归解法

class Solution {
    public int numTilePossibilities(String tiles) {
       char[] chars = tiles.toCharArray();
       List cahrArray = new LinkedList();
       for(int i=0;i<chars.length;i++){
           cahrArray.add(chars[i]);
       }
       Map strMap = new HashMap();
       String str = "";
       checkStr( str, strMap, cahrArray);

       return strMap.size();
    }

    public void checkStr(String str, Map strMap, List chars){

        if(chars.size()!=0){
            for(int i=0;i<chars.size();i++){
                char s = (char)chars.get(i);
                String newstr = str + s;
                strMap.put(newstr,null);
                chars.remove(i);
                checkStr(newstr,strMap,chars);
                chars.add(i,s);
            }
        }

    }
}

效果不理想，速度很慢
Runtime: 25 ms, faster than 32.91% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.

优化一：将LinkedList修改为ArrayList，也就快乐一点点
Runtime: 20 ms, faster than 39.12% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.

优化二：判断重复前缀不需要递归

   public void checkStr(String str, Map strMap, List chars){

        if(chars.size()!=0){
            for(int i=0;i<chars.size();i++){
                char s = (char)chars.get(i);
                String newstr = str + s;
                if(strMap.containsKey(newstr)){
                  continue;
                }
                strMap.put(newstr,null);
                chars.remove(i);
                checkStr(newstr,strMap,chars);
                chars.add(i,s);
            }
        }
}

Runtime: 15 ms, faster than 45.99% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.

目前发现网友最优算法
思路：使用26字母的数组统计字符出现次数，大致原来跟我设计差不多，通过对应字母--和++实现使用和还原。
但是目前疑问就是为什么不判断重复字符串问题呢？直接就总返回值+1？
答案：其实很简单，由于采用该数组模式，相同字母只会取一次作为前缀拼接。
这个相当于我们之前Map判断是否存在一样。

    public int numTilePossibilities(String tiles) {
        int[] count = new int[26];
        for (char c : tiles.toCharArray()) count[c - 'A']++;
        return dfs(count);
    }
    
    int dfs(int[] arr) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (arr[i] == 0) continue;
            sum++;
            arr[i]--;
            sum += dfs(arr);
            arr[i]++;
        }
        return sum;
    }

Runtime: 1 ms, faster than 99.15% of Java online submissions for Letter Tile Possibilities.
Memory Usage: 34.2 MB, less than 100.00% of Java online submissions for Letter Tile Possibilities.