The O(n) Club: Decode String — When Brackets Join the Circus

The O(n) Club: Decode String — When Brackets Join the Circus

⚡ TL;DR

Unravel those cryptic nested bracket strings like 3[a2[c]] into accaccacc. Brute force will have you sobbing in the corner, so wield a stack and treat digits like grown-ups:

// 'I'm just here for moral support, not speed.'
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    // Stuff happens here
}

🧠 How Devs Usually Mess This Up

Decode String looks so innocent—until those brackets get cozy and nestle deep. Some classic missteps:

• Single stack delusion: Trying to cram both numbers and strings into one stack, like stuffing socks and pizza in the same drawer. Spoiler: Smells weird, works worse.
• Digit denial: Only handling single digits. Kids, multi-digit numbers like 42[abc] exist, and they want to be decoded too!
• Recursion for every problem: Looks like an easy win—until you need to escape from recursive bracket inception layers. Unless your call stack is infinite, don’t say I didn’t warn you.

🔍 What’s Actually Going On

This problem is like making ice cream sundaes with Russian nesting dolls. Each opening bracket means “start a new flavor,” every number tells you how many scoops, and by the end, you have a dessert so layered, only a stack (or a therapist) can help untangle it.

So, as we stroll through the string:

• If you see a digit, build the number. Don’t stop at one digit!
• Hit an open bracket? Push the built-up number (num) and collected string (curr) to their own stacks. Clean slate for the next level—it’s inception for loops.
• Letters? Collect them lovingly into your curr builder.
• Find a close bracket? Pop from both your happy stacks, repeat the just-built substring as many times as the number you popped, and tack it back onto whatever was cooking before.

Paranoia tip: Always reset num to zero after a bracket. Multi-digit chaos loves to stick around if you forget.

🛠️ PseudoCode

• Scan through the string, one char at a time.
• If it’s a digit:
  num = num * 10 + (c - '0'); // Keeps building multi-digit numbers
• If ‘[‘ pops up:
  Push num to numStack, current text to strStack. Reset both. You’re new here.
• Letters go into your current StringBuilder. Nothing fancy.
• If ‘]’:
  • Pop number from numStack (times to repeat).
  • Pop last collected string from strStack.
  • Multiply your current built string, append to the previous one, and once again feel smart.

💻 The Code

import java.util.*;
 public class DecodeString {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<StringBuilder> strStack = new Stack<>();
        StringBuilder curr = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                numStack.push(num);
                strStack.push(curr);
                curr = new StringBuilder();
                num = 0;
            } else if (c == ']') {
                int repeat = numStack.pop();
                StringBuilder prev = strStack.pop();
                for (int i = 0; i < repeat; i++) {
                    prev.append(curr);
                }
                curr = prev;
            } else {
                curr.append(c);
            }
        }
        return curr.toString();
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Ignoring multi-digit numbers: Treat 100[cat] right or you’ll get catcat, not a viral sensation.
• Stack overflow on deep recursion: Recursion looks tidy until 999 nested brackets yells “surprise!”. Stack-based iteration keeps your sanity (and your JVM) intact.
• Complexity Confessionals: Time and space are both O(N), where N is the string length. Unless your input is longer than War and Peace, you’re safe.

🧠 Interviewer Brain-Tattoo

If brackets start nesting, don’t panic—nesting calls stacks. Let recursion take a day off, unleash your inner stack whisperer, and decode the day!