The O(n) Club: Letter Case Permutation — Brute Force Meets Java’s Fashion Police

The O(n) Club: Letter Case Permutation — Brute Force Meets Java’s Fashion Police

⚡ TL;DR

You get a string. For every letter, you swap its case and keep all possible combos; digits just sit there, looking unimpressed. Quickest win? DFS (backtracking), which splits your world each time you see a letter — no digit toggling, no nonsense, just 2^K stylish outcomes. Java snippet for the caffeine-powered:

// Bare-bones DFS flavor
List<String> letterCasePermutation(String S) {
    List<String> out = new ArrayList<>();
    backtrack(S.toCharArray(), 0, out);
    return out;
}
// See below for the full drama!

🧠 How Devs Usually Mess This Up

Here’s how not to get famous on Coding Horror: don’t try to permute digits, or treat Java strings like mutable play-dough. Rookie mistake #1 — toggling digits. Spoiler: ‘3’ has no uppercase, not even in hexadecimal. Rookie mistake #2 — you mutate a Java String expecting magic, but end up cloning yourself into One True Permutation land. Been there, debugged that.

🔍 What’s Actually Going On

Think of yourself as a stylist prepping each letter for a runway show: each gets two outfits (upper/lower), while digits are the relatives who show up in Crocs and refuse to participate. DFS lets you explore every combination recursively: when you hit a letter, branch into two — one for each case. Can’t handle recursion? Use iterative BFS and grow permutations level by level. Either way, you’ll have enough letter ensembles to rival a soap opera wedding.

🛠️ PseudoCode

• Start with an empty Java List for results.
• Recursively process each char:
  • If it’s a digit, yawn and move on.
  • If it’s a letter:
    • Option 1: Set to lowercase, recurse.
    • Option 2: Set to uppercase, recurse again.
  • Once you run out of string, dump your hot permutation into the output list.
• Remember: use a char[] (not String) — Java strings are as immovable as tech debt in legacy systems.

💻 The Code

import java.util.*;
 public class LetterCasePermutator {
    public List<String> letterCasePermutation(String S) {
        List<String> result = new ArrayList<>();
        backtrack(S.toCharArray(), 0, result);
        return result;
    }
     private void backtrack(char[] chars, int i, List<String> out) {
        if (i == chars.length) {
            out.add(new String(chars));
            return;
        }
        if (Character.isLetter(chars[i])) {
            chars[i] = Character.toLowerCase(chars[i]);
            backtrack(chars, i + 1, out);
            chars[i] = Character.toUpperCase(chars[i]);
            backtrack(chars, i + 1, out);
        } else {
            backtrack(chars, i + 1, out);
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Digits do not permute — don’t force them; this isn’t a Netflix reboot.
• String immutability in Java — if you mutate a String, Java just nods politely and ignores you. Use char arrays!
• Performance — each letter doubles the output (2^K). If you have a 12-letter string, your solution has more personalities than your product manager.
• Order doesn’t matter — want alphabetical? Great, but that’s your problem. Interviewers don’t care.
• StackOverflow risks — deep recursion might nuke your JVM. The BFS crowd will feel smug but, hey, YOLO.

🧠 Interviewer Brain-Tattoo

“Digits aren’t here to party. For every letter, just fork your code like free pizza — everybody gets both flavors.”