We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Letter Tile Possibilities

Number: 1160

Difficulty: Medium

Paid? No

Companies: Bloomberg, Meta, Amazon, Google

Problem Description

Given a string of lettered tiles, count the number of possible non-empty sequences that can be formed using the letters on the tiles. Each tile may be used at most once per sequence, and the same letter can appear multiple times if provided by the input. For example, for tiles = "AAB", the valid sequences include "A", "B", "AA", "AB", "BA", "AAB", "ABA", and "BAA".

Key Insights

  • Use backtracking to generate all possible sequences.
  • Account for duplicate letters by maintaining a frequency count.
  • At each recursion step, iterate over available letters and choose one, reducing its count to avoid over-counting duplicates.
  • The state space is manageable due to the constraint (tiles.length <= 7).

Space and Time Complexity

Time Complexity: O(n!) in the worst case since we explore all sequences (n is the number of tiles).
Space Complexity: O(n) for recursion depth and frequency storage.

Solution

The approach uses backtracking combined with a frequency dictionary (or hash map) to keep track of the number of times each character is available. Start by counting the frequency of each character in the input string. Then define a recursive function which, for every available character (with count > 0), selects that character, appends it to the current sequence, reduces its available count, and recurses to explore further additions. After recursion, backtrack by restoring the count. Each time a letter is successfully added, count it as a valid sequence. This method avoids generating duplicate sequences by handling duplicate letters correctly using the frequency count.

Code Solutions

# Python solution using recursion with backtracking

def numTilePossibilities(tiles: str) -> int:
    # Count frequencies of each character
    freq = {}
    for ch in tiles:
        freq[ch] = freq.get(ch, 0) + 1

    # Helper function for DFS recursion.
    def backtrack():
        count = 0  # number of sequences starting from this state
        # iterate over characters in frequency dictionary
        for ch in freq:
            if freq[ch] > 0:
                # use this character by decrementing its count
                freq[ch] -= 1
                count += 1  # count current sequence (choosing ch)
                count += backtrack()  # explore further sequences
                # backtrack by restoring the count
                freq[ch] += 1
        return count

    return backtrack()

# Example usage:
tiles = "AAB"
print(numTilePossibilities(tiles))
← Back to All Questions