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 Sam K., 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

More Recursion practice problems

See all Recursion problems →