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 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

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

More Bit Manipulation practice problems

See all Bit Manipulation problems →