Letter Tile Possibilities - Leetcode Solution

Problem Statement: 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 using the letters printed on those tiles.

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 Explanation: The possible sequences are "A", "B", "C", "AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC", "AAA", "AAB", "AAC", "ABA", "ABB", "ABC", "ACA", "ACB", "ACC", "BAA", "BAB", "BAC", "BBA", "BBB", "BBC", "BCA", "BCB", "BCC", "CAA", "CAB", "CAC", "CBA", "CBB", "CBC", "CCA", "CCB", and "CCC".

Solution:

The given problem can be solved by using Depth First Search (DFS) and Backtracking.

The first step is to count the frequency of each letter in the given string ‘tiles’ using a dictionary.

Then, we need to start our search by selecting a character from the dictionary and check if it is possible to make a letter sequence using all its occurrences.

For this, we need to perform DFS and backtracking. We can do this by taking each character one by one from the dictionary, and check if it has any occurrence left. If yes, we can use the character and decrease its count in the dictionary.

After that, we perform DFS, and find all possible non-empty sequences that can be formed using the remaining dictionary. Once we have found all possible combinations using the remaining characters, we backtrack and remove the character from the sequence, so that we can form the next sequence using the remaining characters in the dictionary.

The code for the same is given below:

class Solution: def numTilePossibilities(self, tiles: str) -> int: freq = collections.Counter(tiles) return self.dfs(freq)

def dfs(self, freq: dict) -> int:
    # Initialize count as zero
    count = 0
    
    # Base case for recursion
    for char in freq:
        if freq[char] > 0:
            count += 1
            freq[char] -= 1
            count += self.dfs(freq)
            freq[char] += 1
    
    # Return the total count
    return count

Time Complexity: O(2^N) where N is number of tiles in the input string. This is because, for every character in string we have 2 choices, either we can select it or we can not.

Space Complexity: O(N) where N is number of different characters present in the input string. This is because we create a frequency dictionary to store the frequency count of each character.

Thus, we can use DFS and backtracking approach to solve the above problem.

1