Problem Description

The "Make The String Great" problem requires you to process a string s such that you remove adjacent pairs of characters where one is a lowercase letter and the other is the same letter in uppercase (or vice versa). Specifically, for any two adjacent characters s[i] and s[i+1], if s[i] and s[i+1] are the same letter but with different cases (e.g., 'a' and 'A'), both should be removed. This process is repeated until no such adjacent pairs remain. The final string, after all possible removals, is returned. If the resulting string is empty, return an empty string "".

• Each removal can trigger new possible removals, so the process continues until no more valid pairs exist.
• Only adjacent pairs can be removed at each step.
• There is always one unique valid answer for any input.
• All input consists of English letters only.

Thought Process

At first glance, the problem seems to require checking for adjacent pairs and removing them, repeating the process until the string stabilizes. A brute-force approach would involve scanning the string repeatedly and removing pairs as they are found, but this would be inefficient for longer strings, as each removal could require a new scan from the start.

To optimize, we can think of using a stack data structure. The stack helps us efficiently compare the current character with the last character added. If they form a "bad" pair (same letter, different case), we pop the last character from the stack (removing both). Otherwise, we push the current character onto the stack. This way, we only need to scan the string once, and the stack always contains the current "good" string.

This is analogous to checking for balanced parentheses or removing duplicates, where the stack naturally handles undoing previous steps if a new conflict arises.

Solution Approach

• Step 1: Initialize an empty stack (or a string builder in some languages).
• Step 2: Iterate through each character in the input string s.
• Step 3: For each character, check if the stack is not empty and if the top of the stack forms a "bad" pair with the current character. A "bad" pair means:
  • The two characters are the same letter (ignoring case), and
  • One is uppercase and the other is lowercase.
• Step 4: If a "bad" pair is found, pop the character from the stack (removing both). Otherwise, push the current character onto the stack.
• Step 5: Once all characters have been processed, the stack contains the resulting "good" string. Convert the stack to a string and return it.

Why use a stack? Because it allows us to efficiently undo previous choices if a new adjacent pair forms, without having to rescan the string.

Example Walkthrough

Sample Input: s = "leEeetcode"

1. Start with an empty stack.
2. Add 'l' to the stack. Stack: ['l']
3. Add 'e'. Stack: ['l', 'e']
4. Add 'E'. Now, 'e' and 'E' are adjacent (top of stack and current char), and form a "bad" pair (same letter, different case). Pop 'e'. Stack: ['l']
5. Add 'e'. Stack: ['l', 'e']
6. Add 't'. Stack: ['l', 'e', 't']
7. Add 'c'. Stack: ['l', 'e', 't', 'c']
8. Add 'o'. Stack: ['l', 'e', 't', 'c', 'o']
9. Add 'd'. Stack: ['l', 'e', 't', 'c', 'o', 'd']
10. Add 'e'. Stack: ['l', 'e', 't', 'c', 'o', 'd', 'e']

No more adjacent "bad" pairs remain. Final output: "leetcode"

Time and Space Complexity

• Brute-force approach:
  • Each scan could remove a pair, requiring another full scan. In the worst case, for a string of length n, this could result in O(n²) time complexity.
• Optimized stack approach:
  • Each character is pushed and popped at most once, so the time complexity is O(n), where n is the length of the string.
  • The space complexity is O(n) for the stack, in the case where no removals occur.

Summary

The "Make The String Great" problem is elegantly solved using a stack to efficiently process and remove adjacent letter pairs that differ only in case. This approach avoids repeated rescanning and leverages the stack's properties to handle cascading removals. The final solution is both simple and efficient, with linear time and space complexity, and ensures only valid adjacent pairs are removed until the string is "great".

Code Implementation

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

class Solution {
public:
    string makeGood(string s) {
        string stack = "";
        for (char c : s) {
            if (!stack.empty() && abs(stack.back() - c) == 32) {
                stack.pop_back();
            } else {
                stack.push_back(c);
            }
        }
        return stack;
    }
};
    

class Solution {
    public String makeGood(String s) {
        StringBuilder stack = new StringBuilder();
        for (char c : s.toCharArray()) {
            int len = stack.length();
            if (len > 0 && Math.abs(stack.charAt(len - 1) - c) == 32) {
                stack.deleteCharAt(len - 1);
            } else {
                stack.append(c);
            }
        }
        return stack.toString();
    }
}
    

var makeGood = function(s) {
    let stack = [];
    for (let c of s) {
        if (stack.length > 0 && Math.abs(stack[stack.length - 1].charCodeAt(0) - c.charCodeAt(0)) === 32) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.join('');
};