1544. Make The String Great - Explanation

Problem Link

1. Brute Force

Intuition

A "bad" pair consists of the same letter in different cases adjacent to each other (like "aA" or "Aa"). We repeatedly scan the string looking for such pairs. When we find one, we remove both characters and restart the scan since removing a pair might create a new bad pair from previously non-adjacent characters.

Algorithm

1. Start from index 0 and scan through the string.
2. At each position i, check if the current character and the previous character form a bad pair (same letter, different cases).
3. If a bad pair is found, remove both characters, decrease i by 2 to recheck, and update the string length.
4. Continue until the entire string is scanned without finding any bad pairs.
5. Return the resulting string.

class Solution:
    def makeGood(self, s: str) -> str:
        n = len(s)
        i = 0
        while i < n:
            if i and s[i] != s[i - 1] and s[i].lower() == s[i - 1].lower():
                s = s[:i - 1] + s[i + 1:]
                n -= 2
                i -= 2
            i += 1
        return s

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(n)$

---

2. Stack - I

Intuition

A stack naturally handles the "undo" pattern we need. As we process each character, we compare it with the top of the stack. If they form a bad pair (same letter, different cases), we pop the stack, effectively removing both characters. Otherwise, we push the current character. This handles cascading removals automatically.

Algorithm

1. Initialize an empty stack to build the result.
2. Iterate through each character in the string.
3. For each character, check if the stack is non-empty and the top character forms a bad pair with the current character (same letter when lowercased, but different original characters).
4. If they form a bad pair, pop the stack.
5. Otherwise, push the current character onto the stack.
6. Return the stack contents joined as a string.

class Solution:
    def makeGood(self, s: str) -> str:
        def lower(c):
            if ord(c) < ord('a'):
                return chr(ord('a') + ord(c) - ord('A'))
            return c

        stack = []
        i = 0
        while i < len(s):
            if stack and stack[-1] != s[i] and lower(stack[-1]) == lower(s[i]):
                stack.pop()
            else:
                stack.append(s[i])
            i += 1
        return "".join(stack)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Stack - II

Intuition

We can simplify the bad pair check using ASCII values. In ASCII, the difference between a lowercase letter and its uppercase counterpart is exactly 32 (e.g., 'a' is 97 and 'A' is 65). So if the absolute difference between two characters is 32, they are the same letter in different cases.

Algorithm

1. Initialize an empty stack.
2. For each character in the string:
   • If the stack is non-empty and the absolute ASCII difference between the current character and the stack top is 32, pop the stack.
   • Otherwise, push the current character.
3. Return the stack contents as a string.

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []
        for i in range(len(s)):
            if stack and abs(ord(s[i]) - ord(stack[-1])) == 32:
                stack.pop()
            else:
                stack.append(s[i])
        return "".join(stack)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

4. Two Pointers

Intuition

Instead of using extra space for a stack, we can simulate it in-place using two pointers. The left pointer l represents the "top" of our virtual stack, while the right pointer r scans through the input. Characters before position l form our result. When we find a bad pair, we "pop" by decrementing l.

Algorithm

1. Convert the string to a mutable array and initialize l = 0.
2. For each position r from 0 to the end:
   • If l > 0 and the character at r forms a bad pair with the character at l - 1 (ASCII difference of 32), decrement l to "pop" the pair.
   • Otherwise, copy the character at r to position l and increment l.
3. Return the substring from index 0 to l.

class Solution:
    def makeGood(self, s: str) -> str:
        l = 0
        s = list(s)
        for r in range(len(s)):
            if l > 0 and abs(ord(s[r]) - ord(s[l - 1])) == 32:
                l -= 1
            else:
                s[l] = s[r]
                l += 1
        return ''.join(s[:l])

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the language.