DSA sheet · Stack · Simulation & undo pattern

Make The String Great

The third problem of the simulation and undo pattern, and the teacher says it's almost a copy of Remove All Adjacent Duplicates. The only new thing is which neighbours cancel: the same letter in opposite cases, like "e" next to "E". She shows a brute force that deletes in place and steps back (O(n²)), then the stack (O(n)), and then again the faster string builder version. The real lesson is writing the "do these two cancel?" check correctly.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (stack, undo pattern, upper/lower case)
• Part A · Brute force: delete in place and step back
• Part B · Stack: compare with the top
• Part C · Same idea, builder instead of a stack
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile where you only touch the top, like plates. The last item put in is the first taken out: LIFO (Last In, First Out).

The undo pattern

Read left to right. A new item compares itself with the latest surviving item (the top). If the two cancel, pop and don't push the new one. Otherwise, push. After a pop, the item below becomes the new top, so the chain reaction "the neighbours of a removed pair now touch" is handled automatically.

Upper case, lower case, and comparing them

"e" is lowercase (small), "E" is uppercase (capital). They're the same letter but different characters: 'e' == 'E' is False.

• ch.lower() gives the small version: 'E'.lower() → 'e', 'e'.lower() → 'e'.
• So a.lower() == b.lower() means "same letter, case ignored".
• And a != b means "not the exact same character".

Strings are immutable

Deleting from a string means making a new one (an O(n) copy). Even in a list, deleting from the middle is O(n), because every item to the right shifts one place left. Deleting from the end is O(1). That difference decides the complexity here.

Part A · Brute force: delete in place and step back

LeetCode 1544

1The question in simple words

You get a string s with lowercase and uppercase letters. Two neighbouring characters are a bad pair if they're the same letter but in opposite cases: "eE" or "Ee". Delete bad pairs, again and again, until none is left. The string is then "good" (great). Return it. An empty string also counts as good.

In example 1, once "eE" is deleted we get "leetcode", which has "ee" in it. Both are lowercase, so they're not a bad pair and they stay. Both directions count as bad, though: "eE" and "Ee".

2What the constraints tell us

• 1 ≤ s.length ≤ 100. Tiny. The teacher notes that even O(n²) (10⁴ steps) will be accepted. We optimise for the skill, not because we must.
• s contains only English letters, lower and upper case.
• The answer can be the empty string (example 2).

3Intuition: walk, delete, step back

Stand at index i and look at i and i+1. If they're a bad pair, delete both from the string itself. Everything on the right slides two places left. Then step back one place (i -= 1), because the letter before the deleted pair now touches the letter after it, and they might form a new bad pair. If they're not a bad pair, move forward.

4Building the logic from the examples

Example 1, "leEeetcode"

i = 0: 'l','e' → different letters, move on. i = 1: 'e','E' → same letter, opposite case → delete both → "leetcode". Step back to i = 0: 'l','e' → no. Then 'e','e' → same case, not bad → move on… nothing else is deleted → "leetcode".

Example 2, "abBAcC": why we must step back

1. i = 0: 'a','b' → different letters → i = 1.
2. i = 1: 'b','B' → bad → delete → "aAcC". If we just stayed going forward from i = 1 we'd look at 'A','c' and miss the new pair "aA". So step back: i = 0.
3. i = 0: 'a','A' → bad → delete → "cC". We're already at index 0, so we can't step back; i stays 0.
4. i = 0: 'c','C' → bad → delete → "". Nothing left → answer "".

How do we test "bad pair" in code?

The teacher builds the check in two parts:

• Same letter: convert both to lowercase and compare: a.lower() == b.lower(). "e"/"E" → "e"/"e" ✓. But "e"/"A" → "e"/"a" ✗, which correctly says they're different letters.
• Opposite case: the original characters must be different: a != b. Why? "e" and "e" also pass the lowercase test, but they're both small, which is not a bad pair. If they're equal without conversion, they have the same case.

Cost of this approach

Moving i over the string is O(n). But each deletion in the middle shifts all the letters on its right, another O(n). So the total is O(n²). Fine for n = 100, but not something you'd want for big inputs.

5Approach steps

1. Copy the string into a list arr (so we can delete from it).
2. i = 0. While i < len(arr) - 1 (there is a pair to look at):
3. If arr[i], arr[i+1] is a bad pair → delete both. If i > 0, do i -= 1.
4. Else → i += 1.
5. Return the joined list.

6Code (Python)

class Solution:
    def makeGood(self, s):
        arr = list(s)                      # a string can't be changed, a list can
        i = 0
        while i < len(arr) - 1:            # is there a pair (i, i+1)?
            a, b = arr[i], arr[i + 1]
            if a.lower() == b.lower() and a != b:
                del arr[i:i + 2]           # O(n): the right part shifts left
                if i > 0:
                    i -= 1                 # the new neighbours may now match
            else:
                i += 1
        return "".join(arr)

7Code line by line

8Dry run

s = "abBAcC".

Answer "" ✓

9Complexity & remember

• Time O(n²): up to n positions to check, and each deletion shifts up to n characters.
• Space O(n) in Python for the list copy. (In a language with mutable strings, this would work in place.)

Part B · Stack: compare with the top

1The question (same as Part A)

Same question. New goal: one pass, and only cheap O(1) deletions from the end.

2What the constraints tell us

n ≤ 100, so speed isn't forced on us. But whenever we have to look back at the previous surviving character, the teacher's rule is: use a stack, it gives O(n).

3Intuition: the stack holds the "good so far" part

Keep the characters that survive so far on a stack. The top is the last surviving character. For each new character ch:

• top and ch form a bad pair → pop the top and don't push ch (both vanish);
• otherwise → push ch.

Stepping back in Part A is the same as looking at the new top after a pop. But a pop costs O(1) instead of shifting the whole string.

4Building the logic from the example

"leEeetcode": push l; push e; 'E' vs top 'e' → bad → pop e, skip E; push e; next 'e' vs top 'e' → same case, not bad → push e; then t, c, o, d, e pushed. Stack = l e e t c o d e.

Turning the stack into the answer (her array trick)

The answer must be a string. If you pop items one by one, they come out top first, which is the end of the answer. Adding each popped item to the front, or adding at the back and then reversing, is extra work. The teacher's trick: make an array of size len(stack), and fill it from the last index backwards as you pop. The first item popped (the last character) goes into the last slot, and so on. Then turn the array into a string.

5Approach steps

1. Empty stack. For each ch in s:
2. If the stack isn't empty and (top, ch) is a bad pair → pop. Else → push ch.
3. Make result of size len(stack). Pop everything, filling result from the last index to index 0.
4. Return the joined result.

6Code (Python)

class Solution:
    def makeGood(self, s):
        stack = []
        for ch in s:
            if stack and stack[-1].lower() == ch.lower() and stack[-1] != ch:
                stack.pop()                    # bad pair: both vanish
            else:
                stack.append(ch)

        result = [""] * len(stack)             # one slot per surviving char
        k = len(stack) - 1                     # fill from the back
        while stack:
            result[k] = stack.pop()            # top = last character
            k -= 1
        return "".join(result)

7Code line by line

8Dry run (stack after every step)

s = "abBAcC". Stack drawn left = bottom, right = top.

Answer "" ✓. And for "leEeetcode" the final stack is [l, e, e, t, c, o, d, e]. Popping fills the result from the back: 'e' → slot 7, 'd' → slot 6, 'o' → slot 5, … → "leetcode" ✓.

9Complexity & remember

• Time O(n): each character is pushed once and popped at most once, plus O(n) to build the answer.
• Space O(n): the stack plus the result array.

Part C · Same idea, builder instead of a stack

1What changes

The teacher asks whether we can drop the extra stack and the extra result array. Yes: keep the answer in a string builder from the start and use its last character as the top. Deleting the last character is O(1), just like a pop. At the end, the builder already is the answer in the right order, so we convert it once and we're done. Stack logic, no Stack object.

2Why it's faster

The space is still linear, so in Big-O nothing changes. But it runs faster, for the same reason as in the previous problem: Java's Stack is synchronized (it takes a lock on every push and pop), while a StringBuilder is a plain array with no locks. And there's no copy into a second array at the end.

3Code (Python, builder style)

class Solution:
    def makeGood(self, s):
        sb = []
        for ch in s:
            length = len(sb)
            if (length > 0
                    and sb[length - 1].lower() == ch.lower()   # same letter
                    and sb[length - 1] != ch):                 # opposite case
                del sb[length - 1]          # delete the last char, O(1)
            else:
                sb.append(ch)
        return "".join(sb)

Dry run: identical to Part B. After each step the builder holds exactly what the stack held: [a] → [a,b] → [a] → [ ] → [c] → [ ].

4Complexity & remember

• Time O(n), space O(n) (the builder itself), but less overhead than stack + array.

Part D · Revision page

s = Solution()
print(repr(s.makeGood("leEeetcode")))   # 'leetcode'
print(repr(s.makeGood("abBAcC")))       # ''
print(repr(s.makeGood("s")))            # 's'
print(repr(s.makeGood("aa")))           # 'aa'  (same case stays)
print(repr(s.makeGood("abcCBA")))       # ''

Based on this video: Make The String Great | Stack simulation & undo pattern