What happens if you not handling empty input string?

Code may crash or return incorrect results Fix: Add early return for empty input

What happens if you using string concatenation in recursion without optimization?

Excessive memory usage and slower performance Fix: Use mutable string builder or list to build strings

What happens if you not backtracking properly (forgetting to remove last character)?

Incorrect combinations or duplicates Fix: Remove last character after recursive call to backtrack

What happens if you assuming digit '1' or '0' maps to letters?

Key errors or invalid output Fix: Validate input digits or skip digits without mappings

Interview PrepbacktrackingmediumAmazonFacebookGoogleBloomberg

Letter Combinations of Phone Number

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you have an old phone keypad and want to find all possible letter combinations that a given digit string could represent, like texting on a classic phone.

💡 This problem is a classic example of backtracking where you build all possible combinations by exploring choices at each step. Beginners often struggle because they try to solve it iteratively or get confused about how to explore all branches systematically.

📋

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. The mapping of digits to letters is the same as on the telephone buttons (2 maps to 'abc', 3 to 'def', etc.). Note that digit '1' does not map to any letters.

1 ≤ digits.length ≤ 4digits[i] is a digit in the range ['2', '9']

💡

Example

Input"23"

Outputadaeafbdbebfcdcecf

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

Empty input string → returns empty list
Single digit input like '2' → returns letters mapped to that digit
Input with repeated digits like '22' → returns combinations with repeated letters
Maximum length input '2345' → returns all combinations from four digits

⚠️

Common Mistakes

Not handling empty input string

Code may crash or return incorrect results

✅ Add early return for empty input

Using string concatenation in recursion without optimization

Excessive memory usage and slower performance

✅ Use mutable string builder or list to build strings

Not backtracking properly (forgetting to remove last character)

Incorrect combinations or duplicates

✅ Remove last character after recursive call to backtrack

Assuming digit '1' or '0' maps to letters

Key errors or invalid output

✅ Validate input digits or skip digits without mappings

Not testing with repeated digits

Missed bugs in combination generation

✅ Test inputs like '22' to ensure repeated digits handled correctly

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem deeply by exploring all possible letter combinations without optimization. It builds intuition for backtracking.

Intuition

At each digit, try every possible letter it maps to, then recursively do the same for the next digit until all digits are processed.

Algorithm

Create a mapping from digits to letters.
Define a recursive function that takes the current index and the current combination string.
If the current index equals the length of digits, add the combination to results.
Otherwise, for each letter mapped from the current digit, recurse with the next index and updated combination.

💡 The recursion builds combinations step-by-step, and the base case collects complete combinations.

</>

Code

def letterCombinations(digits):
    if not digits:
        return []
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    result = []
    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        for char in digit_map[digits[index]]:
            backtrack(index + 1, path + char)
    backtrack(0, '')
    return result

# Example usage:
if __name__ == '__main__':
    print(letterCombinations('23'))

Line Notes

if not digits:Handle empty input early to avoid unnecessary processing and return empty list

digit_map = {...}Map digits to their corresponding letters as per phone keypad to know possible letters

result = []Initialize list to store all possible letter combinations

def backtrack(index, path):Define recursive helper to build combinations by exploring letters at each digit

if index == len(digits):Base case: all digits processed, add current combination to results

for char in digit_map[digits[index]]:Try each letter mapped from current digit to explore all branches

backtrack(index + 1, path + char)Recurse to next digit with updated combination string

import java.util.*;
public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        String[] digitMap = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), digitMap, result);
        return result;
    }
    private void backtrack(String digits, int index, StringBuilder path, String[] digitMap, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }
        String letters = digitMap[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(digits, index + 1, path, digitMap, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCombinations("23"));
    }
}

Line Notes

if (digits == null || digits.length() == 0)Check for empty input to return early and avoid unnecessary processing

String[] digitMap = ...Array maps digit characters to their letters for quick lookup

List<String> result = new ArrayList<>();Initialize list to store all letter combinations

backtrack(digits, 0, new StringBuilder(), digitMap, result);Start recursion from first digit with empty path builder

if (index == digits.length())Base case: all digits processed, add current combination to results

String letters = digitMap[digits.charAt(index) - '0'];Get letters mapped from current digit

for (char c : letters.toCharArray())Iterate over letters mapped from current digit to explore all options

path.append(c);Add current letter to path before recursion

backtrack(digits, index + 1, path, digitMap, result);Recurse to next digit with updated path

path.deleteCharAt(path.length() - 1);Backtrack by removing last letter after recursion to explore other branches

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

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result;
        string path;
        backtrack(digits, 0, path, digitMap, result);
        return result;
    }
private:
    void backtrack(const string& digits, int index, string& path, const vector<string>& digitMap, vector<string>& result) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        string letters = digitMap[digits[index] - '0'];
        for (char c : letters) {
            path.push_back(c);
            backtrack(digits, index + 1, path, digitMap, result);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<string> res = sol.letterCombinations("23");
    for (auto& s : res) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

if (digits.empty()) return {};Return empty vector immediately if input is empty to avoid processing

vector<string> digitMap = {...};Map digits to corresponding letters for quick lookup

vector<string> result;Initialize vector to store all letter combinations

string path;Mutable string to build current combination efficiently

void backtrack(...)Recursive helper function to build combinations by exploring letters at each digit

if (index == digits.size())Base case: all digits processed, add current path to results

string letters = digitMap[digits[index] - '0'];Get letters mapped from current digit

for (char c : letters)Try each letter mapped from current digit to explore all branches

path.push_back(c);Add letter to path before recursion

backtrack(digits, index + 1, path, digitMap, result);Recurse to next digit with updated path

path.pop_back();Backtrack by removing last letter after recursion to explore other branches

var letterCombinations = function(digits) {
    if (!digits.length) return [];
    const digitMap = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };
    const result = [];
    function backtrack(index, path) {
        if (index === digits.length) {
            result.push(path);
            return;
        }
        for (const char of digitMap[digits[index]]) {
            backtrack(index + 1, path + char);
        }
    }
    backtrack(0, '');
    return result;
};

// Example usage:
console.log(letterCombinations('23'));

Line Notes

if (!digits.length) return [];Handle empty input by returning empty array early

const digitMap = {...};Object maps digits to their letters for quick lookup

const result = [];Initialize array to store all letter combinations

function backtrack(index, path)Recursive function to build combinations by exploring letters at each digit

if (index === digits.length)Base case: all digits processed, add current combination to results

for (const char of digitMap[digits[index]])Iterate over letters mapped from current digit to explore all options

backtrack(index + 1, path + char);Recurse to next digit with updated combination string

⏱

Complexity

TimeO(4^n * n)

SpaceO(n)

Each digit can map up to 4 letters (e.g., '7' or '9'), so total combinations are up to 4^n. Each combination is length n, so appending or creating strings takes O(n) time per combination. The recursion stack and path use O(n) space.

💡 For n=3 digits, this means up to 64 combinations, each length 3, so roughly 192 operations to build all strings. The recursion depth is n, so space is proportional to input length.

Interview Verdict: Accepted

Though brute force explores all combinations, it is efficient enough for typical input sizes and is a solid baseline solution.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	`O(4^n * n)`	`O(n)`	Yes (deep recursion for large n)	Yes	Mention only - good for explaining basics
2. Backtracking with Mutable Path	`O(4^n * n)`	`O(n)`	Yes	Yes	Code this approach in 95% of interviews
3. Iterative Using Queue	`O(4^n * n)`	`O(4^n * n)`	No	Yes	Mention as alternative, rarely code

Practice

(1/5)

1. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

3. The following BFS code attempts to remove invalid parentheses but contains a subtle bug:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                # BUG: removing characters other than parentheses
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

What is the bug in this code?

medium

A. The found flag is reset inside the inner loop, causing premature termination

B. The is_valid function incorrectly returns True for unbalanced strings

C. The visited set is not updated correctly, causing duplicates

D. The code removes characters even if they are not '(' or ')', expanding search unnecessarily

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Analyze approaches

Final Answer:

Quick Check:

Solution

Step 1: Count possible states

Step 2: Analyze per-state cost

Final Answer:

Quick Check:

Solution

Step 1: Identify character removal condition

Step 2: Consequence of bug

Final Answer:

Quick Check:

Solution

Step 1: Understand digit reuse impact

Step 2: Prevent infinite loops

Step 3: Evaluate options

Final Answer:

Quick Check:

Solution

Step 1: Understand new constraint

Step 2: Modify algorithm accordingly

Step 3: Evaluate other options

Final Answer:

Quick Check:

Ready to prove it?