Letter Combinations of Phone Number

📋

Letter Combinations of Phone Number

Edge cases:

</>

IDE

def letterCombinations(digits: str) -> list:public List<String> letterCombinations(String digits)vector<string> letterCombinations(string digits)function letterCombinations(digits)

def letterCombinations(digits):
    # Write your solution here
    pass

class Solution {
    public List<String> letterCombinations(String digits) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> letterCombinations(string digits) {
    // Write your solution here
    return {};
}

function letterCombinations(digits) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce"]Missing last combination 'cf' due to off-by-one error in loop over letters.✅ Change loop condition to include all letters: for char in digit_map[digits[index]]:

Wrong: ["a", "b", "c"]Returns only letters for first digit ignoring subsequent digits (greedy approach).✅ Implement full backtracking recursion that processes all digits, not just the first.

Wrong: ["pw", "px", "py", "qw", "qx", "qy", "rw", "rx", "ry", "sw", "sx", "sy"]Digits with 4 letters ('7' and '9') handled as if they have 3 letters, missing last letters 'pz' and 'qz' etc.✅ Iterate over full letter string length for digits '7' and '9'.

Wrong: []No base case for empty input, causing function to return empty list or error.✅ Add early return: if not digits: return []

Wrong: ["a", "b", "c", "a", "b", "c"]Duplicates due to incorrect handling of repeated digits or global state not reset.✅ Ensure recursion path is local and no global state causes duplicates.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before tackling edge cases.

Review your recursion to ensure it explores all letter combinations fully.

Optimize your solution to handle the maximum input size within time limits.

t1_01basic

Input"23"

Expected["ad","ae","af","bd","be","bf","cd","ce","cf"]

⏱ Performance - must finish in 2000ms

Digit '2' maps to 'abc', digit '3' maps to 'def'. All combinations of letters from these two sets are returned.

💡 Think about mapping each digit to its possible letters and combining them.

💡 Use backtracking to build all possible strings by choosing one letter per digit.

💡 Implement a recursive function that appends letters for each digit until the string length matches input length.

Why it failed: Output missing some combinations or incorrect order due to incomplete recursion or wrong mapping. Fix by ensuring recursion explores all letters for each digit and collects all results.

✓ Correctly generates all letter combinations using backtracking.

t1_02basic

Input"79"

Expected["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"]

⏱ Performance - must finish in 2000ms

Digit '7' maps to 'pqrs', digit '9' maps to 'wxyz'. All combinations of letters from these two sets are returned.

💡 Check the digit-to-letters mapping carefully, especially digits with 4 letters like '7' and '9'.

💡 Backtracking must handle digits mapping to different number of letters.

💡 Ensure recursion loops over all letters for each digit and combines them properly.

Why it failed: Missing combinations due to incorrect handling of digits with 4 letters or off-by-one errors in loops. Fix by iterating over all letters mapped to each digit.

✓ Correctly handles digits with varying letter counts and generates all combinations.

t2_01edge

Input""

Expected[]

⏱ Performance - must finish in 2000ms

Empty input string returns empty list as no digits to map.

💡 Consider what the output should be if input is empty.

💡 Check if your code handles empty input by returning an empty list immediately.

💡 Add a base case to return [] if digits string is empty.

Why it failed: Returns non-empty list or errors on empty input due to missing base case. Fix by adding early return for empty input.

✓ Correctly returns empty list for empty input.

t2_02edge

Input"2"

Expected["a","b","c"]

⏱ Performance - must finish in 2000ms

Single digit '2' maps to letters 'abc', so output is those letters individually.

💡 Test your code with single digit input to verify base recursion works.

💡 Ensure recursion or iteration handles single digit by returning all mapped letters.

💡 Check that output length matches number of letters mapped to the digit.

Why it failed: Output missing letters or returns empty due to incorrect base case or loop. Fix by handling single digit case properly.

✓ Correctly returns all letters for single digit input.

t2_03edge

Input"22"

Expected["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

⏱ Performance - must finish in 2000ms

Repeated digit '2' twice means combinations of letters from 'abc' twice, including repeated letters.

💡 Check if your code handles repeated digits correctly by combining letters for each position.

💡 Backtracking should not skip repeated digits or reuse letters incorrectly.

💡 Ensure recursion depth matches input length and explores all letter combinations.

Why it failed: Output missing repeated letter combinations or duplicates due to incorrect recursion or memoization. Fix by treating each digit independently in recursion.

✓ Correctly generates all combinations including repeated letters.

t2_04edge

Input"2345"

Expected["adgj","adgk","adgl","adhj","adhk","adhl","adij","adik","adil","aegj","aegk","aegl","aehj","aehk","aehl","aeij","aeik","aeil","afgj","afgk","afgl","afhj","afhk","afhl","afij","afik","afil","bdgj","bdgk","bdgl","bdhj","bdhk","bdhl","bdij","bdik","bdil","begj","begk","begl","behj","behk","behl","beij","beik","beil","bfgj","bfgk","bfgl","bfhj","bfhk","bfhl","bfij","bfik","bfil","cdgj","cdgk","cdgl","cdhj","cdhk","cdhl","cdij","cdik","cdil","cegj","cegk","cegl","cehj","cehk","cehl","ceij","ceik","ceil","cfgj","cfgk","cfgl","cfhj","cfhk","cfhl","cfij","cfik","cfil"]

⏱ Performance - must finish in 2000ms

Maximum length input with digits '2','3','4','5' mapping to 'abc','def','ghi','jkl'. All combinations must be generated.

💡 Check if your code handles maximum input length correctly without truncation.

💡 Ensure recursion depth and loops cover all digits and their letters.

💡 Fix any premature termination or incorrect base case that limits output length.

Why it failed: Output incomplete or truncated due to incorrect recursion depth or base case. Fix by ensuring recursion continues until all digits processed.

✓ Correctly generates all combinations for maximum input length.

t3_01corner

Input"234"

Expected["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]

⏱ Performance - must finish in 2000ms

Digits '2', '3', '4' map to 'abc', 'def', 'ghi' respectively. All combinations must be generated.

💡 Beware of greedy approaches that pick only one letter per digit without exploring all combinations.

💡 Backtracking must explore all branches, not just the first letter of each digit.

💡 Fix greedy bug by using recursion or iteration that tries all letters for each digit.

Why it failed: Greedy approach returns fewer combinations by choosing only first letters. Fix by implementing full backtracking exploring all letter options per digit.

✓ Correctly generates all combinations by exploring all letter choices.

t3_02corner

Input"79"

Expected["pw","px","py","pz","qw","qx","qy","qz","rw","rx","ry","rz","sw","sx","sy","sz"]

⏱ Performance - must finish in 2000ms

Digits '7' and '9' map to letters with 4 letters each. Tests handling of digits with 4 letters.

💡 Check if your code assumes all digits map to 3 letters, which is incorrect for '7' and '9'.

💡 Verify loops or recursion iterate over all letters mapped to each digit, including 4-letter digits.

💡 Fix off-by-one errors in loops to include all letters for digits '7' and '9'.

Why it failed: Output missing letters for digits with 4 letters due to loop boundary errors. Fix by iterating over full letter string length for each digit.

✓ Correctly handles digits with 4 letters and generates all combinations.

t3_03corner

Input"2345"

Expected["adgj","adgk","adgl","adhj","adhk","adhl","adij","adik","adil","aegj","aegk","aegl","aehj","aehk","aehl","aeij","aeik","aeil","afgj","afgk","afgl","afhj","afhk","afhl","afij","afik","afil","bdgj","bdgk","bdgl","bdhj","bdhk","bdhl","bdij","bdik","bdil","begj","begk","begl","behj","behk","behl","beij","beik","beil","bfgj","bfgk","bfgl","bfhj","bfhk","bfhl","bfij","bfik","bfil","cdgj","cdgk","cdgl","cdhj","cdhk","cdhl","cdij","cdik","cdil","cegj","cegk","cegl","cehj","cehk","cehl","ceij","ceik","ceil","cfgj","cfgk","cfgl","cfhj","cfhk","cfhl","cfij","cfik","cfil"]

⏱ Performance - must finish in 2000ms

Maximum length input with digits '2','3','4','5' mapping to 'abc','def','ghi','jkl'. All combinations must be generated.

💡 Check if your code handles maximum input length correctly without truncation.

💡 Ensure recursion depth and loops cover all digits and their letters.

💡 Fix any premature termination or incorrect base case that limits output length.

Why it failed: Output incomplete or truncated due to incorrect recursion depth or base case. Fix by ensuring recursion continues until all digits processed.

✓ Correctly generates all combinations for maximum input length.

t4_01performance

Input{"_description":"n=4 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=4, maximum allowed. Algorithm must run in O(4^n * n) time within 2 seconds.

💡 Backtracking has exponential time complexity O(4^n * n).

💡 Optimize by pruning or iterative approaches if possible.

💡 Avoid unnecessary string concatenations inside recursion.

Why it failed: Algorithm times out due to exponential complexity. Fix by optimizing recursion or using iterative approach.

✓ Algorithm runs within time limit for maximum input size.

Practice

1. Consider the following bitmask-based backtracking code for n=4. After placing the first queen at row 0, column 1, what is the value of available_positions at row 1 (second recursive call)?

easy

A. 0b1010 (binary 10 decimal)

B. 0b1100 (binary 12 decimal)

C. 0b1001 (binary 9 decimal)

D. 0b1000 (binary 8 decimal)

Solution

1. Step 1: Trace first queen placement at row 0, col 1

   Position bitmask = 0b0010 (decimal 2). Update cols=0b0010, diag1=(0b0010)<<1=0b0100, diag2=(0b0010)>>1=0b0001.

2. Step 2: Compute available_positions at row 1

   available_positions = (0b1111) & ~(cols | diag1 | diag2) = 0b1111 & ~(0b0010 | 0b0100 | 0b0001) = 0b1111 & ~0b0111 = 0b1111 & 0b1000 = 0b1000 (decimal 8). The only available position is column 3 (bit 3).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask after first queen excludes cols 1, diag1 shifted left, diag2 shifted right [OK]

Hint: Bitmask tracks attacked columns and diagonals precisely [OK]

Common Mistakes:

• Miscomputing diagonal shifts
• Off-by-one in bit length
• Confusing cols with diag masks

2. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?

easy

A. Backtracking that explores all substring partitions and checks palindrome validity dynamically

B. Dynamic programming that counts the number of palindromic substrings without generating partitions

C. Greedy approach that picks the longest palindrome substring at each step

D. Breadth-first search that generates partitions level by level without palindrome checks

Solution

1. Step 1: Understand problem requirements

   The problem requires generating all palindrome partitions, not just counting or finding one.

2. Step 2: Identify suitable algorithm

   Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with palindrome checks finds all partitions [OK]

Hint: Backtracking explores all partitions with palindrome pruning [OK]

Common Mistakes:

• Assuming greedy longest palindrome picks all partitions
• Confusing counting palindromes with generating partitions
• Ignoring palindrome checks in BFS

3. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

4. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column constraint is relaxed), but diagonal attacks still apply. Which modification to the bitmask backtracking algorithm correctly adapts to this variant?

hard

A. Remove the column bitmask tracking and only track diagonal attacks in recursion

B. Keep column bitmask but allow multiple queens by resetting it each row

C. Use a greedy approach placing queens in any column without pruning

D. Track columns as before but ignore diagonal bitmasks

Solution

1. Step 1: Understand relaxed constraints

   Since columns can have multiple queens, column bitmask is no longer needed to prune placements.

2. Step 2: Adapt pruning to only diagonal attacks

   Keep diag1 and diag2 bitmasks to prune diagonal conflicts, but remove column mask from available_positions calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Removing column mask allows multiple queens per column while still pruning diagonals [OK]

Hint: Relaxed constraints remove column pruning, keep diagonal pruning [OK]

Common Mistakes:

• Resetting column mask each row incorrectly
• Ignoring diagonal pruning
• Using greedy without pruning

5. If the problem changes so that numbers can be reused multiple times in the permutation (i.e., repetition allowed), which modification to the algorithm is correct?

hard

A. Use a greedy approach to pick the smallest available number at each step until length n is reached.

B. Use the same factorial-based approach but do not remove numbers from the list after selection.

C. Modify factorial computations to account for repeated elements and use a multiset permutation formula.

D. Generate all permutations with backtracking and stop when the k-th is found, since factorial indexing no longer applies.

Solution

1. Step 1: Understand repetition impact

   Allowing reuse breaks the factorial number system assumption because permutations count changes drastically.

2. Step 2: Identify correct approach

   Backtracking with early stop can generate permutations with repetition and find the k-th one, as direct factorial indexing is invalid.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Factorial indexing fails with repetition; backtracking is correct fallback [OK]

Hint: Factorial indexing requires unique elements; repetition breaks it [OK]

Common Mistakes:

• Trying to reuse factorial indexing without adjustment
• Ignoring repetition changes permutation count
• Assuming greedy works for k-th permutation with repetition