Letter Tile Possibilities

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.8 kB
1
Indexable
Never
class Solution {
    //combination of subset II and Permutation. Check  video for the same.
    int count = 0;
    public int numTilePossibilities(String tiles) {
        List<Character>temp = new ArrayList<>();
        char[] chars = tiles.toCharArray();
        Arrays.sort(chars);
        tiles = String.valueOf(chars);
        generateSubsets(tiles,0,temp,0);
        return count - 1;
    }
    private void generateSubsets(String tiles, int index, List<Character> temp, int size) {
        if(index == tiles.length()) {
            System.out.println("generated subset = " + temp);
            calculatePermutationCount(temp);
            return;
        }

        //Yes Condition -  I am taking this element
        temp.add(tiles.charAt(index));
        generateSubsets(tiles, index+1, temp, size+1);
        temp.remove(size);

        //No Condition - I am not taking this element
        while(index < tiles.length() - 1 && tiles.charAt(index) == tiles.charAt(index+1)) {
            index++;
        }
        generateSubsets(tiles, index+1, temp, size);
    }

    private void calculatePermutationCount(List<Character> s) {
        generatePermutations(s,0); 
    }

    private void generatePermutations(List<Character> s, int index) {
        if(index == s.size()) {
           // System.out.println("    Permutation = " + s);
            count++;
        }
        int[] freq = new int[26];
        for(int i = index; i < s.size(); i++) {
            if(freq[s.get(i) - 'A'] == 0) {
                swap(s, index, i);
                generatePermutations(s, index+1);
                swap(s, index, i);
            }
            freq[s.get(i) - 'A']++; 
        }
    }

    private void swap(List<Character> s, int i, int j) {
        char temp = s.get(i);
        s.set(i,s.get(j));
        s.set(j,temp);
    }

}