Letter Tile Possibilities - Practice Coding Problems

Letter Tile Possibilities - Problem

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.

Note: You may use each tile at most once per sequence.

Input & Output

Example 1 — Basic Case

$ Input: tiles = "AAB"

› Output: 8

💡 Note: Possible sequences: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA". Total of 8 sequences.

Example 2 — All Same Characters

$ Input: tiles = "AAABBC"

› Output: 188

💡 Note: With frequencies A:3, B:2, C:1, we can form many sequences of lengths 1-6. Each length has unique permutations based on character frequencies.

Example 3 — Single Character

$ Input: tiles = "V"

› Output: 1

💡 Note: Only one sequence possible: "V"

Constraints

1 ≤ tiles.length ≤ 7
tiles consists of uppercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Tiles

Given string of letter tiles like 'AAB'

Generate Sequences

Form all possible non-empty sequences using each tile at most once

Count Unique

Return total number of unique sequences

Key Takeaway

🎯 Key Insight: Use backtracking with frequency counting to systematically generate all possible sequences without duplicates

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to use backtracking with frequency counting to generate all possible sequences without duplicates. The optimal approach uses a frequency map to track available characters and backtracking to systematically build sequences. Time: O(∑k!/∏freq_i!), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Permutations	O(2ⁿ × n!)	O(2ⁿ × n!)	Generate all possible permutations of all lengths and count unique sequences
Backtracking with Frequency Map	O(∑(k! / ∏(freq_i)!))	O(n)	Use backtracking to generate sequences while tracking character frequencies

Brute Force - Generate All Permutations — Algorithm Steps

Generate all possible subsequences
For each subsequence, generate all permutations
Count unique sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsequences

Create all possible combinations of tiles

Create Permutations

Generate all arrangements for each combination

Count Unique

Remove duplicates and count total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SEQUENCES 10000

char sequences[MAX_SEQUENCES][20];
int sequenceCount = 0;

int isUnique(const char* seq) {
    for (int i = 0; i < sequenceCount; i++) {
        if (strcmp(sequences[i], seq) == 0) {
            return 0;
        }
    }
    return 1;
}

void addSequence(const char* seq) {
    if (isUnique(seq) && sequenceCount < MAX_SEQUENCES) {
        strcpy(sequences[sequenceCount], seq);
        sequenceCount++;
    }
}

void generatePermutations(char* chars, int n, char* current, int pos, int* used) {
    if (pos == n) {
        current[pos] = '\0';
        addSequence(current);
        return;
    }
    
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            current[pos] = chars[i];
            generatePermutations(chars, n, current, pos + 1, used);
            used[i] = 0;
        }
    }
}

void generateCombinations(char* tiles, int n, char* current, int pos, int start, int targetLength) {
    if (pos == targetLength) {
        char temp[20];
        int used[20] = {0};
        generatePermutations(current, targetLength, temp, 0, used);
        return;
    }
    
    for (int i = start; i < n; i++) {
        current[pos] = tiles[i];
        generateCombinations(tiles, n, current, pos + 1, i + 1, targetLength);
    }
}

int solution(char* tiles) {
    sequenceCount = 0;
    int n = strlen(tiles);
    
    for (int length = 1; length <= n; length++) {
        char current[20];
        generateCombinations(tiles, n, current, 0, 0, length);
    }
    
    return sequenceCount;
}

int main() {
    char tiles[20];
    fgets(tiles, sizeof(tiles), stdin);
    tiles[strcspn(tiles, "\n")] = 0;
    
    int result = solution(tiles);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n!)

Generate 2^n subsequences, each with up to n! permutations

⚠ Quadratic Growth

Space Complexity

O(2ⁿ × n!)

Store all generated sequences

⚠ Quadratic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler