Decode String

📋

Decode String

Edge cases:

</>

IDE

def decodeString(s: str) -> str:public String decodeString(String s)string decodeString(string s)function decodeString(s)

def decodeString(s: str) -> str:
    # Write your solution here
    pass

class Solution {
    public String decodeString(String s) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

string decodeString(string s) {
    // Write your solution here
    return "";
}

function decodeString(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrectly decoded string missing repeated segmentsNot handling repeat counts properly or missing multiplication after ']' bracket.✅ Apply decoded substring repetition immediately after closing bracket and reset repeat count.

Wrong: Output with partial repeats or wrong nestingIncorrect stack management for nested brackets causing wrong substring repeats.✅ Use stack to store previous string and repeat count at each '[' and decode fully at each ']'.

Wrong: Crashes or errors on empty input or no bracket stringsNo base case for empty string or strings without digits/brackets.✅ Add checks to return input as is if empty or no brackets found.

Wrong: Timeout on large inputsRecursive or inefficient string concatenation causing exponential time.✅ Implement iterative stack-based approach and use efficient string builders.

✓

Test Cases

Focus on handling empty strings and strings without brackets correctly.

Practice nested decoding and managing multiple stack frames.

Optimize your solution to run efficiently on large inputs.

t1_01basic

Input"3[a]2[bc]"

Expected"aaabcbc"

⏱ Performance - must finish in 2000ms

3[a] means 'a' repeated 3 times, 2[bc] means 'bc' repeated twice.

💡 Focus on how numbers and brackets define repeated substrings.

💡 Use a stack to keep track of current string and repeat counts.

💡 Push current string and count on stack when '[' is encountered, pop and repeat when ']' is found.

Why it failed: Incorrect output means the code likely mishandles repeat counts or bracket parsing. Fix by correctly pushing and popping from stack and applying repeats only after closing bracket.

✓ Correctly handles basic repeat and concatenation with stack.

t1_02basic

Input"2[abc]3[cd]ef"

Expected"abcabccdcdcdef"

⏱ Performance - must finish in 2000ms

2[abc] repeats 'abc' twice, 3[cd] repeats 'cd' thrice, followed by 'ef'.

💡 Remember to concatenate decoded segments in order.

💡 Track multiple repeat segments and plain characters outside brackets.

💡 Ensure the decoded string accumulates correctly after each bracketed section.

Why it failed: If output misses parts or repeats incorrectly, likely concatenation or stack unwinding is wrong. Fix by appending decoded segments properly after each ']' bracket.

✓ Correctly concatenates multiple repeated and plain segments.

t2_01edge

Input""

Expected""

⏱ Performance - must finish in 2000ms

Empty string input should return empty string output.

💡 Check how your code handles empty input.

💡 Make sure no indexing or stack operations occur on empty string.

💡 Return empty string immediately if input is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding base case to return '' if input is empty.

✓ Handles empty input gracefully.

t2_02edge

Input"abc"

Expected"abc"

⏱ Performance - must finish in 2000ms

String without any brackets or digits returns itself unchanged.

💡 Check if code handles strings without any repeats.

💡 Ensure plain characters are appended correctly without modification.

💡 Return input as is if no brackets or digits found.

Why it failed: Code incorrectly modifies or fails on strings without brackets. Fix by treating plain characters as normal and appending them directly.

✓ Correctly returns strings without repeats unchanged.

t2_03edge

Input"100[a]"

Expected"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

⏱ Performance - must finish in 2000ms

Repeat 'a' 100 times as specified by the number before brackets.

💡 Handle multi-digit repeat counts correctly.

💡 Parse full number before '[' to get repeat count.

💡 Repeat decoded substring exactly k times.

Why it failed: Code fails on multi-digit repeat counts or repeats wrong number of times. Fix by accumulating digits until '[' before decoding substring.

✓ Correctly handles large repeat counts.

t2_04edge

Input"1[z]"

Expected"z"

⏱ Performance - must finish in 2000ms

Repeat count of 1 should return the substring unchanged.

💡 Check that repeat count 1 does not alter the substring.

💡 Ensure multiplication by 1 returns the substring as is.

💡 Avoid off-by-one errors in repeat count parsing.

Why it failed: Code may skip or alter substring when repeat count is 1. Fix by correctly applying multiplication even when count is 1.

✓ Correctly handles repeat count of 1.

t3_01corner

Input"2[a2[b2[c]]]"

Expected"abccbccabccbcc"

⏱ Performance - must finish in 2000ms

Nested repeats: innermost 2[c], then 2[bcc], then 2[a bcc bcc].

💡 Nested brackets require stack to handle multiple levels.

💡 Push current string and count at each '[' and pop at each ']'.

💡 Multiply decoded substring by count at each closing bracket.

Why it failed: Code fails nested decoding or multiplies wrong substring. Fix by correctly managing stack frames for nested brackets and applying repeats at each level.

✓ Correctly decodes nested repeated substrings.

t3_02corner

Input"3[a]2[bc]4[ab]"

Expected"aaabcbcabababab"

⏱ Performance - must finish in 2000ms

Multiple repeated segments concatenated: 3[a], 2[bc], 4[ab].

💡 Ensure all repeated segments are decoded and concatenated in order.

💡 Do not reset decoded string prematurely between segments.

💡 Handle multiple bracketed repeats in sequence.

Why it failed: Code resets decoded string after first segment or misses later repeats. Fix by accumulating decoded segments continuously.

✓ Correctly concatenates multiple repeated segments.

t3_03corner

Input"10[a2[b]]"

Expected"abbabbabbabbabbabbabbabbabbabb"

⏱ Performance - must finish in 2000ms

Decode inner 2[b] to 'bb', then repeat 'abb' 10 times.

💡 Handle nested repeats with different repeat counts.

💡 Apply inner repeats before outer repeats.

💡 Use stack to decode inner bracket before outer.

Why it failed: Code confuses order of repeats or concatenation. Fix by decoding inner bracket fully before applying outer repeat count.

✓ Correctly handles nested repeats with different counts.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000 with nested or repeated patterns must decode within 2 seconds.

💡 Use iterative stack-based approach to avoid recursion overhead.

💡 Avoid repeated string concatenation; use efficient string builders.

💡 Time complexity should be O(n * max_k), optimize inner loops.

Why it failed: Solution times out due to exponential or recursive overhead. Fix by implementing iterative stack approach and efficient string concatenation.

✓ Solution runs within time limits using optimized stack-based decoding.

Practice

1. Given the following code for a queue implemented with two stacks, what is the output of the last print statement?

q = MyQueue()
q.push(10)
q.push(20)
print(q.pop())
q.push(30)
print(q.peek())

easy

A. 30

B. 20

C. 10

D. Error due to empty stack

Solution

1. Step 1: Trace pop() after pushing 10 and 20

   pop_stack is empty, transfer push_stack [10,20] reversed to pop_stack [20,10], pop() returns 10.

2. Step 2: After pushing 30, peek() checks pop_stack which has [20], so peek returns 20

   After pop(), pop_stack has [20], push_stack has [30]. peek() does not transfer because pop_stack is not empty, so peek returns 20.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   pop() returns 10, peek() returns 20 [OK]

Hint: pop transfers once, peek uses existing pop_stack [OK]

Common Mistakes:

• Assuming peek returns 10 after pop
• Forgetting transfer only when pop_stack empty

2. Consider the following Python function that computes the largest rectangle area in a histogram using a monotonic stack approach. Given the input heights = [2, 1, 5], what is the value of the variable right after computing the right boundaries (just before calculating max_area)?

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [1, 3, 3]

D. [3, 3, 3]

Solution

1. Step 1: Trace right boundary computation for i=2 (height=5)

   Stack is empty, so right[2] = n = 3, stack = [2]

2. Step 2: Trace i=1 (height=1)

   Pop indices with height >= 1: pop 2 (height=5), stack empty, right[1] = 3, stack = [1]

3. Step 3: Trace i=0 (height=2)

   Stack top is 1 (height=1) < 2, so right[0] = 1, stack = [1,0]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Right boundaries correctly reflect next smaller bar indices [OK]

Hint: Right boundaries found by scanning from right with stack [OK]

Common Mistakes:

• Confusing indices or off-by-one in right boundary
• Not clearing stack before right boundary pass

3. Given the following Python code for checking valid parentheses, what is the return value when the input string is "([)]"?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

easy

A. False

B. True

C. Raises an exception

D. Depends on input length

Solution

1. Step 1: Trace input "([)]" through the code

   Push '(' then push '['. Next char is ')', expected to match '[' but pairs[')'] = '(', top of stack is '[' -> mismatch -> return False immediately.

2. Step 2: Confirm final output

   Function returns False as soon as mismatch is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mismatch detected at third character -> returns False [OK]

Hint: Mismatch causes immediate False return [OK]

Common Mistakes:

• Assuming order doesn't matter and returning True incorrectly

4. What is the time complexity of the getMin() operation in the single stack with encoded minimum values approach for the Minimum Stack problem, and why?

medium

A. O(1), because the minimum value is stored and updated during push and pop operations.

B. O(n), because it needs to scan the entire stack to find the minimum.

C. O(log n), because the stack maintains a balanced structure to track minimums.

D. O(n), because the encoded differences require decoding all elements to find the minimum.

Solution

1. Step 1: Understand getMin() operation

   In the encoded stack approach, minVal is updated on every push/pop, so getMin() just returns minVal.

2. Step 2: Analyze complexity

   Since getMin() returns a stored variable without iteration, it runs in O(1) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   getMin() is a direct variable access, no loops [OK]

Hint: getMin() returns stored minVal updated on push/pop [OK]

Common Mistakes:

• Assuming getMin scans stack
• Confusing encoded values require decoding
• Thinking balanced tree needed for min tracking

5. Suppose the sliding window maximum problem is modified so that the window size k can vary dynamically during the iteration. Which of the following approaches correctly adapts the monotonic deque solution to handle this efficiently?

hard

A. Adjust the window boundary checks and remove indices outside the current window size dynamically without rebuilding the deque

B. Rebuild the deque from scratch each time the window size changes

C. Switch to a max heap data structure since deque cannot handle variable window sizes

D. Use a brute force approach for variable window sizes to avoid complexity

Solution

1. Step 1: Understand dynamic window size impact

   Window boundaries change, so indices outside the current window must be removed accordingly.

2. Step 2: Adapt monotonic deque maintenance

   Instead of rebuilding, update boundary checks and pop indices outside the new window size dynamically.

3. Step 3: Evaluate alternatives

   Rebuilding deque or switching to heap is inefficient; brute force is too slow.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dynamic boundary checks maintain O(n) amortized complexity [OK]

Hint: Update boundary removals dynamically, avoid rebuilding [OK]

Common Mistakes:

• Rebuilding deque wastes time
• Assuming heap is better for variable k