Make The String Great

Difficulty: Easy | Acceptance: 68.50% | Paid: No Topics: String, Stack

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2 s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa. To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can do this process until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique.

• Examples
• Constraints
• Brute Force Simulation
• Stack Approach

Examples

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, remove "eE" from "leEeetcode" to get "leetcode".

Input: s = "abBAcC"
Output: ""
Explanation: 
- Remove "abBAcC" -> "aAcC"
- Remove "aAcC" -> "cC"
- Remove "cC" -> ""

Input: s = "s"
Output: "s"

Constraints

1 <= s.length <= 100
s consists of lower and upper case English letters.

Brute Force Simulation

Intuition Repeatedly scan the string from left to right. If a “bad” pair of adjacent characters (same letter, different case) is found, remove them and restart the scan from the beginning, as the removal might create a new bad pair with the previous character.

Steps

• Iterate while the string can be modified.
• In each pass, loop through the string indices.
• Check if s[i] and s[i+1] form a bad pair (ASCII difference is 32).
• If found, remove the substring and break the inner loop to restart.
• If no pair is found after a full pass, the string is “great”.

class Solution:
    def makeGood(self, s: str) -> str:
        while True:
            found = False
            for i in range(len(s) - 1):
                if abs(ord(s[i]) - ord(s[i+1])) == 32:
                    s = s[:i] + s[i+2:]
                    found = True
                    break
            if not found:
                break
        return s

Complexity

• Time: O(n²) - In the worst case (e.g., “abBA”), we might scan the string repeatedly.
• Space: O(n) - To store the modified string.
• Notes: Simple to implement but inefficient for longer strings.

Stack Approach

Intuition Use a stack to simulate the process efficiently. Iterate through the string, pushing characters onto the stack. If the current character forms a bad pair with the top of the stack, pop the stack instead of pushing. This handles the “cascading” removals automatically.

Steps

• Initialize an empty stack.
• Iterate through each character in the string.
• Check if the stack is not empty and the current character cancels the top of the stack (ASCII difference is 32).
• If they cancel, pop the stack.
• Otherwise, push the current character onto the stack.
• Convert the stack to a string and return it.

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)

Complexity

• Time: O(n) - Each character is processed exactly once.
• Space: O(n) - In the worst case, the stack stores all characters.
• Notes: Optimal solution for this problem.