Skip to main content

784. Letter Case Permutation

medium

Given a string of letters and digits, return every variation by toggling each letter's case. The bitmask iteration trick walks 2^k masks where k is the letter count.

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

Count the letters k. The answer has exactly 2^k strings.

Hint 2

Each letter independently is upper or lower — that's a bit. Map each letter position to one bit in a mask.

Hint 3

Iterate mask from 0 to (1 << k) - 1, then walk s emitting each character with case toggled iff the corresponding bit is set.

Hint 4

ASCII trick: lowercase and uppercase versions of the same letter differ only at bit 5 (0x20). XOR a letter byte with 0x20 to toggle its case.

Solution approach

Reveal approach

Bitmask iteration with the 0x20 case-flip trick. First scan s once to collect the indices of letter positions into a list letter_idx of length k. For mask from 0 to (1 << k) - 1, build the candidate string by copying s and, for each bit i set in mask, XOR the byte at letter_idx[i] with 0x20 (which flips between upper and lower case in ASCII). Append to result. Total work is 2^k strings * length-n copy = O(n * 2^k) time and matching output space. The 0x20 trick avoids the if-isalpha-then-toupper branching and keeps the inner loop branch-free.

Complexity

Time
O(n * 2^k)
Space
O(n * 2^k) output

Related patterns

  • bit-manipulation
  • backtracking

Related problems

Asked at

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

  • Microsoft
  • Yelp

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →