Make The String Great

How it works

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.

Steps

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.

Complexity

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

Things to watch for

Checking Only for Case Difference Without Same Letter

A "bad" pair requires two conditions: the characters must be the same letter AND have different cases. Checking only s[i] != s[i-1] is insufficient because characters like 'a' and 'B' are different but not a bad pair. You must also verify they are the same letter when case is ignored.

Off-by-One Errors in Index Management

When removing a bad pair and backtracking, the index must be decremented by 2 (not 1) to recheck the newly adjacent characters. Using i -= 1 instead of i -= 2 causes the algorithm to skip potential new bad pairs created by the removal.

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])

class Solution {
public:
    string makeGood(string s) {
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            if (l > 0 && abs(s[r] - s[l - 1]) == 32) {
                l--;
            } else {
                s[l++] = s[r];
            }
        }
        return s.substr(0, l);
    }
};