Letter Case Permutation — Medium Problem & Solution

s consists of English letters and digits. You may switch any letter of s to lowercase or to uppercase, independently of the others; digits stay as they are.

Difficulty: Medium
Topics: Strings, Bit Manipulation, Backtracking
Asked at: Amazon, Microsoft, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

s consists of English letters and digits. You may switch any letter of s to lowercase or to uppercase, independently of the others; digits stay as they are.

Return every distinct string you can produce this way, sorted in ascending ASCII order (digits before uppercase letters, uppercase before lowercase).

Example 1

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

Example 2

Input: s = "7K"
Output: ["7K","7k"]

Example 3

Input: s = "2026"
Output: ["2026"]
Explanation: No letters, so the string itself is the only result.

Constraints

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

How to solve Letter Case Permutation

Each letter is an independent binary choice, so the answer is a product of 2^k choices. A depth-first build (or a bitmask over the letter positions) enumerates them; a final byte-order sort fixes the order.

Approach

Walk s with an index i and a working character buffer.
If i == n, record the buffer as a string.
If s[i] is a letter, set it to lowercase and recurse, then to uppercase and recurse; otherwise just recurse.
Sort the collected strings by character code.

Why it works

Every combination of cases is a distinct path through the binary choices, and different paths differ at some letter's case, so all 2^k strings are distinct and none is missed.

Complexity

Time — O(2^k · n log(2^k)) with the sort
Space — O(2^k · n) for the output

Pitfalls

Sort by character code, not with a locale-aware comparison: 'B' must come before 'a'.
Digits do not branch — branching on them duplicates strings.
The input may already contain uppercase letters; both cases are still produced.

Reference solution

Python

from typing import List

def letterCasePermutation(s: str) -> List[str]:
    out = ['']
    for c in s:
        if c.isalpha():
            out = [p + c.lower() for p in out] + [p + c.upper() for p in out]
        else:
            out = [p + c for p in out]
    out.sort()
    return out

JavaScript

var letterCasePermutation = function(s) {
    var chars = s.split('');
    var out = [];
    var dfs = function(i) {
        if (i === chars.length) {
            out.push(chars.join(''));
            return;
        }
        var c = chars[i];
        if (/[a-zA-Z]/.test(c)) {
            chars[i] = c.toLowerCase();
            dfs(i + 1);
            chars[i] = c.toUpperCase();
            dfs(i + 1);
            chars[i] = c;
        } else {
            dfs(i + 1);
        }
    };
    dfs(0);
    out.sort();
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 424 strings problems · the whole catalogue

Learn the technique: Strings · Bit Manipulation