Jobs

Interviews

Discussions

Letter Tile Possibilities

Medium

Asked by:

More companies

31 views

Topics:

StringsRecursionDynamic Programming

You have n 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: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

Constraints:

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

Try coding it in LeetCode

Letter Tile Possibilities

Medium

Asked by:

31 views

Topics:

StringsRecursionDynamic Programming

You have n 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: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input `tiles` string be empty or null?
Are the tiles case-sensitive, or should I treat 'A' and 'a' as the same?
What is the maximum length of the `tiles` string?
Are we only concerned with the *number* of possible strings, or do we need to generate the strings themselves?
Should the permutations be distinct? For example, if the input is 'AA', is 'A' counted once or twice?

Brute Force Solution

Approach

The brute force method for this problem is all about trying out every single combination of letter tiles to see which ones form valid sequences. We generate every possible sequence of tiles, count them, and make sure not to count any sequence twice. It's like trying every possible anagram.

Here's how the algorithm would work step-by-step:

Start with an empty sequence of tiles.
Pick one tile and add it to the sequence. This is one possibility.
Now, go back and pick a different tile and add it to the empty sequence. This is another possibility.
Next, take the first tile you chose and add another tile to it, creating a two-tile sequence. Try every possible second tile.
Repeat this process, adding tiles one at a time to existing sequences, until you've created all possible sequences using all available tiles.
Each time you create a new sequence, check if you've already created that same sequence before. If you have, don't count it again.
Count each unique sequence that you've created.
The final number is the total count of unique sequences that can be formed using the tiles.

Code Implementation

def letter_tile_possibilities(tiles):
    unique_sequences = set()

    def generate_sequences(current_sequence, remaining_tiles):
        # Add current sequence, skip if already exists
        if current_sequence not in unique_sequences:
            unique_sequences.add(current_sequence)
        else:
            return

        # Base case: No more tiles to choose
        if not remaining_tiles:
            return

        for index, tile in enumerate(remaining_tiles):
            # Create new sequence by adding the tile
            new_sequence = current_sequence + tile

            # Remove the used tile for the next recursive call
            remaining_tiles_copy = list(remaining_tiles)
            remaining_tiles_copy.pop(index)
            generate_sequences(new_sequence, remaining_tiles_copy)

    generate_sequences("", list(tiles))

    # Do not count the empty initial sequence
    return len(unique_sequences) - 1

Big(O) Analysis

Time Complexity

O(n!) – The algorithm generates all possible sequences (permutations) of letter tiles. In the worst case, where all the tiles are distinct, it considers sequences of length 1, 2, 3, up to n, where n is the number of tiles. The number of permutations grows factorially. Therefore, the total number of operations is proportional to n! (n factorial), which represents the number of ways to arrange n distinct items. Thus, the time complexity is O(n!).

Space Complexity

O(N) – The primary driver of auxiliary space is the recursion depth and the storage of sequences. In the worst-case scenario, where all tiles are distinct, the algorithm could explore sequences up to length N, where N is the number of tiles. Each level of recursion stores a partial sequence, so the recursion stack can grow up to a depth of N. Furthermore, the algorithm implicitly stores a set (or similar data structure) to keep track of already generated sequences, which could potentially store all possible sequences, which grows at most proportionally with N. Thus, the space complexity is O(N).

Optimal Solution

Approach

To find all the unique arrangements of tiles, the best approach involves systematically building arrangements tile by tile. It avoids redundancy by only counting arrangements in a specific order and reuses computed results, making it much faster than trying every single combination.

Here's how the algorithm would work step-by-step:

Count how many of each tile you have to begin with.
Start building a potential arrangement by trying each available tile as the first tile.
For each choice of first tile, reduce the count of that tile by one, since you've used it.
Keep building the arrangement recursively: try each remaining tile as the next tile, reducing its count each time.
Each time you complete an arrangement, count it as one of the valid possibilities. Make sure you don't count any duplicates.
After trying all possible tiles at a particular position in the arrangement, increase the count of the tile you picked back up by one (backtracking). This allows it to be used in other arrangements.
Repeat these steps until you have tried all possible arrangements.
Store arrangements in a set as you find them to automatically handle counting the duplicates

Code Implementation

def letter_tile_possibilities(tiles):
    tile_counts = {}
    for tile in tiles:
        tile_counts[tile] = tile_counts.get(tile, 0) + 1

    unique_arrangements = set()

    def backtrack(current_arrangement):
        # Add arrangement to set to avoid duplicates
        if current_arrangement:
            unique_arrangements.add(current_arrangement)

        for tile, count in tile_counts.items():
            if count > 0:
                # Decrement the count since we are using this tile
                tile_counts[tile] -= 1

                backtrack(current_arrangement + tile)

                # Backtrack: Restore the count for other branches
                tile_counts[tile] += 1

    backtrack("")
    return len(unique_arrangements)

Big(O) Analysis

Time Complexity

O(N!) – The algorithm explores all possible permutations of the input tiles. Let N be the number of tiles. In the worst case, the recursion explores all possible arrangements, where each level of the recursion branches out to consider each remaining tile. This branching factor is multiplied at each subsequent level, leading to a factorial growth in the number of explored paths. Therefore, the time complexity is proportional to the number of permutations, which is O(N!). The use of a set to eliminate duplicates does not fundamentally change the overall exponential nature of the time complexity.

Space Complexity

O(N) – The provided solution utilizes a set to store unique arrangements, and a count array to store the frequency of each tile. The size of the set can grow up to N! in the worst case, where N is the number of tiles. However, the problem statement implicitly bounds the number of distinct tiles. The count array stores the frequency of each distinct tile, which contributes O(1) space since the number of possible characters is fixed (A-Z). The recursive calls create a call stack of at most N depth in the worst case (all tiles are different), hence O(N). Therefore, the dominant factor is the call stack, leading to O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 as there are no tile possibilities.
Input string with a single character	Return 1 as there is only one possibility: the single tile itself.
Input string with all identical characters (e.g., 'AAAA')	The algorithm should correctly count permutations, avoiding overcounting due to duplicates.
Maximum length input string (e.g., length of 7 as given in constraints)	Ensure the algorithm's time complexity remains acceptable and does not lead to stack overflow in case of recursion.
Input string with a large number of duplicate characters	The algorithm must efficiently handle duplicates to prevent combinatorial explosion and overcounting.
Input string contains special characters or non-alphabetic characters	The problem statement constraints dictate only uppercase letters are valid input.
Very skewed distribution of characters (e.g., 'AAABCDE')	The algorithm should correctly generate all possible combinations regardless of the distribution.
Input string such that the number of possibilities overflows integer limit	The problem constraints limits the string length such that integer overflow won't be a problem.

Null or empty input string

How to Handle:

Return 0 as there are no tile possibilities.

Input string with a single character

How to Handle:

Return 1 as there is only one possibility: the single tile itself.

Input string with all identical characters (e.g., 'AAAA')

How to Handle:

The algorithm should correctly count permutations, avoiding overcounting due to duplicates.

Maximum length input string (e.g., length of 7 as given in constraints)

How to Handle:

Ensure the algorithm's time complexity remains acceptable and does not lead to stack overflow in case of recursion.

Input string with a large number of duplicate characters

How to Handle:

The algorithm must efficiently handle duplicates to prevent combinatorial explosion and overcounting.

Input string contains special characters or non-alphabetic characters

How to Handle:

The problem statement constraints dictate only uppercase letters are valid input.

Very skewed distribution of characters (e.g., 'AAABCDE')

How to Handle:

The algorithm should correctly generate all possible combinations regardless of the distribution.

Input string such that the number of possibilities overflows integer limit

How to Handle:

The problem constraints limits the string length such that integer overflow won't be a problem.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input `tiles` string be empty or null?
Are the tiles case-sensitive, or should I treat 'A' and 'a' as the same?
What is the maximum length of the `tiles` string?
Are we only concerned with the *number* of possible strings, or do we need to generate the strings themselves?
Should the permutations be distinct? For example, if the input is 'AA', is 'A' counted once or twice?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty sequence of tiles.
Pick one tile and add it to the sequence. This is one possibility.
Now, go back and pick a different tile and add it to the empty sequence. This is another possibility.
Next, take the first tile you chose and add another tile to it, creating a two-tile sequence. Try every possible second tile.
Repeat this process, adding tiles one at a time to existing sequences, until you've created all possible sequences using all available tiles.
Each time you create a new sequence, check if you've already created that same sequence before. If you have, don't count it again.
Count each unique sequence that you've created.
The final number is the total count of unique sequences that can be formed using the tiles.

Code Implementation

def letter_tile_possibilities(tiles):
    unique_sequences = set()

    def generate_sequences(current_sequence, remaining_tiles):
        # Add current sequence, skip if already exists
        if current_sequence not in unique_sequences:
            unique_sequences.add(current_sequence)
        else:
            return

        # Base case: No more tiles to choose
        if not remaining_tiles:
            return

        for index, tile in enumerate(remaining_tiles):
            # Create new sequence by adding the tile
            new_sequence = current_sequence + tile

            # Remove the used tile for the next recursive call
            remaining_tiles_copy = list(remaining_tiles)
            remaining_tiles_copy.pop(index)
            generate_sequences(new_sequence, remaining_tiles_copy)

    generate_sequences("", list(tiles))

    # Do not count the empty initial sequence
    return len(unique_sequences) - 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Count how many of each tile you have to begin with.
Start building a potential arrangement by trying each available tile as the first tile.
For each choice of first tile, reduce the count of that tile by one, since you've used it.
Keep building the arrangement recursively: try each remaining tile as the next tile, reducing its count each time.
Each time you complete an arrangement, count it as one of the valid possibilities. Make sure you don't count any duplicates.
After trying all possible tiles at a particular position in the arrangement, increase the count of the tile you picked back up by one (backtracking). This allows it to be used in other arrangements.
Repeat these steps until you have tried all possible arrangements.
Store arrangements in a set as you find them to automatically handle counting the duplicates

Code Implementation

def letter_tile_possibilities(tiles):
    tile_counts = {}
    for tile in tiles:
        tile_counts[tile] = tile_counts.get(tile, 0) + 1

    unique_arrangements = set()

    def backtrack(current_arrangement):
        # Add arrangement to set to avoid duplicates
        if current_arrangement:
            unique_arrangements.add(current_arrangement)

        for tile, count in tile_counts.items():
            if count > 0:
                # Decrement the count since we are using this tile
                tile_counts[tile] -= 1

                backtrack(current_arrangement + tile)

                # Backtrack: Restore the count for other branches
                tile_counts[tile] += 1

    backtrack("")
    return len(unique_arrangements)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 as there are no tile possibilities.
Input string with a single character	Return 1 as there is only one possibility: the single tile itself.
Input string with all identical characters (e.g., 'AAAA')	The algorithm should correctly count permutations, avoiding overcounting due to duplicates.
Maximum length input string (e.g., length of 7 as given in constraints)	Ensure the algorithm's time complexity remains acceptable and does not lead to stack overflow in case of recursion.
Input string with a large number of duplicate characters	The algorithm must efficiently handle duplicates to prevent combinatorial explosion and overcounting.
Input string contains special characters or non-alphabetic characters	The problem statement constraints dictate only uppercase letters are valid input.
Very skewed distribution of characters (e.g., 'AAABCDE')	The algorithm should correctly generate all possible combinations regardless of the distribution.
Input string such that the number of possibilities overflows integer limit	The problem constraints limits the string length such that integer overflow won't be a problem.

Null or empty input string

How to Handle:

Return 0 as there are no tile possibilities.

Input string with a single character

How to Handle:

Return 1 as there is only one possibility: the single tile itself.

Input string with all identical characters (e.g., 'AAAA')

How to Handle:

The algorithm should correctly count permutations, avoiding overcounting due to duplicates.

Maximum length input string (e.g., length of 7 as given in constraints)

How to Handle:

Ensure the algorithm's time complexity remains acceptable and does not lead to stack overflow in case of recursion.

Input string with a large number of duplicate characters

How to Handle:

The algorithm must efficiently handle duplicates to prevent combinatorial explosion and overcounting.

Input string contains special characters or non-alphabetic characters

How to Handle:

The problem statement constraints dictate only uppercase letters are valid input.

Very skewed distribution of characters (e.g., 'AAABCDE')

How to Handle:

The algorithm should correctly generate all possible combinations regardless of the distribution.

Input string such that the number of possibilities overflows integer limit

How to Handle:

The problem constraints limits the string length such that integer overflow won't be a problem.