Skip to main content

784. Letter Case Permutation

medium

Given a string, return every string you can form by toggling the case of each letter (digits stay put). Two-way recursive branching at each letter — the cleanest demonstration of 'binary choice' backtracking.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. Return the output in any order.

Constraints

  • 1 <= s.length <= 12
  • s consists of lowercase English letters, uppercase English letters, and digits.

Examples

Example 1

Input
s = "a1b2"
Output
["a1b2","a1B2","A1b2","A1B2"]

Example 2

Input
s = "3z4"
Output
["3z4","3Z4"]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse with (index, currentPath). At each index, branch on whether the character is a letter.

Hint 2

Letter: two branches — lowercase and uppercase.

Hint 3

Digit: one branch — append the digit.

Hint 4

Base case: index == s.length -> snapshot.

Solution approach

Reveal approach

Recursive helper(index, path): if index == s.length, snapshot path.join() to result and return. Let c = s[index]. If c is a digit: append c, recurse(index + 1, path), pop. If c is a letter: append c.toLowerCase(), recurse(index + 1, path), pop; then append c.toUpperCase(), recurse(index + 1, path), pop. Output has 2^k entries where k is the number of letters in s. Time is O(2^k * n) — exponential in letter count, linear copy at each leaf. Space is O(n) recursion stack plus the output. An equivalent iterative bitmask approach: for mask in [0, 2^k), use bit positions to decide upper/lower at each letter — useful when k is small.

Complexity

Time
O(2^k * n) where k = letter count
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • binary-choice

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Letter Case Permutation and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →