Definition
- Letter Case Permutation – generates every string obtainable by changing the case of zero or more letters while leaving digits unchanged.
- Subsets doubling pattern – the list of variants doubles at each letter position and stays the same at each digit.
- Size snapshot – snapshot the list size before each letter to fork only the variants that existed before this round.
- Independent copies – each forked variant must be a separate copy of the backing array to prevent shared mutation.
- Result size – 2^k variants where k is the number of letters in the input.
At the National Bank of India, a reference code like a2B may be typed by customers in mixed case. Support needs every case variant to match against records while leaving digits alone. Starting from the original code, each letter position doubles the variant list while digit positions leave it unchanged.
Understanding the Concepts
What is the Letter Case Permutation problem?
Given a string containing letters and digits, generate all possible strings that can be formed by changing the case of zero or more letters. Digits remain unchanged. For example, "a1b" produces ["a1b", "a1B", "A1b", "A1B"].
package com.bank.core;
// Input: "a1b"
// Letters: 'a' at index 0, 'b' at index 2
// 2^2 = 4 variants:
// "a1b", "a1B", "A1b", "A1B"
Why does the doubling technique work?
This is a Subsets-pattern problem. Each letter is a binary choice: keep the original case or flip it. Digits have no choice. Processing characters left to right, the list of variants doubles at each letter and stays the same at each digit. After all characters are processed, the list contains all 2^k variants where k is the number of letters.
package com.bank.core;
// Input: "a1b"
// Start: ["a1b"]
// Process index 0 ('a' is letter):
// Fork each variant: flip 'a' to 'A'
// List: ["a1b", "A1b"]
// Process index 1 ('1' is digit):
// No fork, list unchanged: ["a1b", "A1b"]
// Process index 2 ('b' is letter):
// Fork each variant: flip 'b' to 'B'
// List: ["a1b", "A1b", "a1B", "A1B"]
How do you implement it?
Seed the list with the original string as a character array. For each index, check if the character is a letter. If it is, snapshot the current list size, then for each existing variant, create a copy and flip the case at that index.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class LetterCasePermutation {
public List<String> letterCasePermutation(String s) {
List<char[]> variants = new ArrayList<>();
variants.add(s.toCharArray());
for (int i = 0; i < s.length(); i++) {
if (Character.isLetter(s.charAt(i))) {
int size = variants.size(); // snapshot before forking
for (int j = 0; j < size; j++) {
char[] copy = variants.get(j).clone();
copy[i] = flipCase(copy[i]);
variants.add(copy);
}
}
}
List<String> result = new ArrayList<>();
for (char[] v : variants) result.add(new String(v));
return result;
}
private char flipCase(char c) {
if (Character.isUpperCase(c)) return Character.toLowerCase(c);
return Character.toUpperCase(c);
}
public static void main(String[] args) {
LetterCasePermutation solver = new LetterCasePermutation();
System.out.println(solver.letterCasePermutation("a1b"));
System.out.println(solver.letterCasePermutation("3z4"));
}
}
[a1b, A1b, a1B, A1B]
[3z4, 3Z4]
Why must each fork be an independent copy?
If you modify a shared character array, flipping one variant's character corrupts all variants that share the same backing array. Using .clone() on the character array ensures each fork is independent.
package com.bank.core;
// WRONG: shared reference
char[] shared = variants.get(j); // same reference
shared[i] = flipCase(shared[i]); // corrupts the original!
variants.add(shared); // both entries point to the same array
// CORRECT: independent copy
char[] copy = variants.get(j).clone();
copy[i] = flipCase(copy[i]);
variants.add(copy); // separate array
Why snapshot the list size before each letter?
Without snapshotting, the inner loop would iterate over variants added during the same round, causing each new variant to be forked again and producing duplicates or incorrect results. Snapshotting the size ensures you only fork variants that existed before this letter's processing.
package com.bank.core;
// WRONG: no snapshot
for (int j = 0; j < variants.size(); j++) { // size grows during loop!
char[] copy = variants.get(j).clone();
copy[i] = flipCase(copy[i]);
variants.add(copy); // infinite loop!
}
// CORRECT: snapshot size
int size = variants.size();
for (int j = 0; j < size; j++) {
char[] copy = variants.get(j).clone();
copy[i] = flipCase(copy[i]);
variants.add(copy);
}
How does the backtracking alternative work?
Instead of the iterative doubling approach, you can use recursion. At each index, if the character is a digit, recurse to the next index. If it is a letter, recurse twice: once with the original case and once with the flipped case.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class LetterCasePermutationRecursive {
public List<String> letterCasePermutation(String s) {
List<String> result = new ArrayList<>();
backtrack(s.toCharArray(), 0, result);
return result;
}
private void backtrack(char[] chars, int index, List<String> result) {
if (index == chars.length) {
result.add(new String(chars));
return;
}
if (Character.isDigit(chars[index])) {
backtrack(chars, index + 1, result);
} else {
// Keep original case
backtrack(chars, index + 1, result);
// Flip case
chars[index] = flipCase(chars[index]);
backtrack(chars, index + 1, result);
// Restore original (backtrack)
chars[index] = flipCase(chars[index]);
}
}
private char flipCase(char c) {
if (Character.isUpperCase(c)) return Character.toLowerCase(c);
return Character.toUpperCase(c);
}
}
What are the edge cases?
Edge cases include: all digits (only one variant, the original), all letters (2^n variants), empty string (one empty variant), and single character.
package com.bank.core;
// Edge case 1: "123" -> ["123"] (no letters, one variant)
// Edge case 2: "abc" -> 2^3 = 8 variants
// Edge case 3: "" -> [""] (one empty variant)
// Edge case 4: "A" -> ["A", "a"] (two variants)
// Edge case 5: "a1B2c" -> 2^3 = 8 variants (3 letters)
What about a banking use case?
At the National Bank of India, support needs to match customer-typed reference codes against stored records. Customers may type codes in any case, so the system generates all case variants while keeping digits fixed.
package com.bank.service;
import java.util.List;
import java.util.Set;
import java.util.HashSet;
public class ReferenceCodeMatcher {
private final LetterCasePermutation solver = new LetterCasePermutation();
public boolean matchesAnyVariant(String typedCode, Set<String> storedCodes) {
List<String> variants = solver.letterCasePermutation(typedCode);
for (String variant : variants) {
if (storedCodes.contains(variant)) {
System.out.println("Matched variant: " + variant);
return true;
}
}
return false;
}
public static void main(String[] args) {
ReferenceCodeMatcher matcher = new ReferenceCodeMatcher();
Set<String> stored = new HashSet<>();
stored.add("NBI2024x");
matcher.matchesAnyVariant("nbi2024X", stored);
}
}
Matched variant: NBI2024x
What should a senior engineer know?
A senior engineer should note that only alphabetic characters fork the result, so a code with many digits and few letters produces a small result even for long strings. The iterative doubling approach avoids recursion overhead and is often preferred in interviews for its clarity. Using a bit mask over the letter positions is an alternative: each bitmask from 0 to 2^k - 1 determines which letters to flip, generating all variants without explicit list management.
package com.bank.core;
// Senior notes:
// 1. Result size: 2^k where k = number of letters
// 2. Many digits + few letters -> small result even for long strings
// 3. Bitmask alternative: iterate 0 to 2^k - 1, flip letter at bit i
// 4. Iterative doubling avoids recursion stack overhead
// 5. Character.isLetter, toLowerCase, toUpperCase handle Unicode correctly
Visual Overview
Doubling technique for "a1B":
Start: ["a1B"]
Index 0: 'a' is a letter
┌───────────────────────────────────┐
│ Snapshot size = 1 │
│ Fork variant 0: flip 'a' -> 'A' │
│ List: ["a1B", "A1B"] │
└───────────────────────────────────┘
Index 1: '1' is a digit
┌───────────────────────────────────┐
│ Skip, no forking │
│ List: ["a1B", "A1B"] │
└───────────────────────────────────┘
Index 2: 'B' is a letter
┌───────────────────────────────────┐
│ Snapshot size = 2 │
│ Fork variant 0: flip 'B' -> 'b' │
│ Fork variant 1: flip 'B' -> 'b' │
│ List: ["a1B", "A1B", "a1b", "A1b"]│
└───────────────────────────────────┘
Final: 4 variants (2^2 letters)
Growth pattern:
┌─────────┐ ┌─────────┐ ┌─────────┐
│ "a1B" │ 'a' │ "a1B" │ '1' │ "a1B" │
│ │────→│ "A1B" │────→│ "A1B" │
│ │ │ │skip │ │
│ 1 item │ │ 2 items │ │ 2 items │
└─────────┘ └─────────┘ └────┬────┘
│ 'B'
▼
┌─────────┐
│ "a1B" │
│ "A1B" │
│ "a1b" │
│ "A1b" │
│ 4 items │
└─────────┘
Key Takeaway
Letter Case Permutation generates every string obtainable by changing the case of zero or more letters in the input while leaving digits unchanged. You process the string character by character over a growing list of variants seeded with the original. For a digit, the list is unchanged. For a letter, you snapshot the current size, then for each existing variant you create an independent copy with that letter's case flipped, doubling the list.
The two critical implementation details are the size snapshot and the independent copy. Without snapshotting the size before each letter, the inner loop would iterate over newly added variants and create an infinite loop or incorrect duplicates. Without cloning the character array, flipping a character in a shared array would corrupt other variants that reference the same backing data.
The result count is 2^k where k is the number of letters, so a code with many digits and few letters stays small even for long strings. The backtracking alternative processes the string recursively, branching at each letter, but the iterative doubling approach is often cleaner in interviews. A bitmask alternative iterates from 0 to 2^k - 1, using each bit to decide which letters to flip.
At the National Bank of India, the support team used this to match customer-typed reference codes against stored records. Customers might type codes in any combination of upper and lower case, so the system generated all case variants while keeping digits fixed and checked each against the stored set. The iterative doubling produced all variants efficiently for codes with only a few letter positions.
Remember one sentence: for each letter, duplicate all existing variants with that letter's case flipped; for each digit, do nothing.
---