LeetCode 1544 - Make The String Great

LeetCode Problem 1544

Difficulty: 🟢 Easy
Topics: String, Stack

Solution

Problem Understanding

The problem asks us to process a string s consisting of lowercase and uppercase English letters, removing pairs of adjacent letters that are the same character but differ in case. Specifically, any pair where one character is lowercase and the adjacent character is its uppercase counterpart (or vice versa) is considered "bad." We must remove such pairs iteratively until no more bad pairs remain, producing a "good" string.

The input s is guaranteed to have a length between 1 and 100, which is small enough to allow simple iterative solutions without performance concerns. The output should be the final good string, and the problem guarantees uniqueness. An empty string is considered valid if all characters are removed.

Key points include recognizing that removal of a pair may create new bad pairs that need to be resolved in subsequent iterations. Edge cases include strings that are already good, strings with alternating upper/lower letters that cancel completely, and single-character strings.

Approaches

A brute-force approach would repeatedly scan the string for bad adjacent pairs, remove them, and repeat until no bad pairs remain. While correct, this approach is inefficient because repeated scanning and string slicing lead to O(n²) time complexity in the worst case.

The optimal solution leverages a stack to process the string in a single pass. The idea is to iterate through each character and compare it with the top of the stack. If the character forms a bad pair with the stack's top, pop the stack. Otherwise, push the character onto the stack. This method ensures that we always resolve adjacent conflicts immediately and process the string in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scan and remove bad pairs until string is good
Optimal	O(n)	O(n)	Single-pass stack solution, resolving conflicts immediately

Algorithm Walkthrough

1. Initialize an empty stack to hold characters of the currently "good" string as we iterate.
2. Iterate through each character c in the input string s.
3. If the stack is not empty and the top character of the stack forms a bad pair with c (i.e., abs(ord(stack[-1]) - ord(c)) == 32), pop the stack to remove the conflicting pair.
4. Otherwise, push c onto the stack.
5. After processing all characters, convert the stack into a string by joining its elements.
6. Return the resulting string as the final good string.

Why it works: The stack maintains the invariant that it contains a good string at all times. Any time a bad pair is found, it is immediately removed, which guarantees that at the end, no bad pairs remain. The process is complete because each character is either added or removed exactly once.

Python Solution

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)

The Python solution uses a list as a stack. For each character, it checks whether it forms a bad pair with the stack's top. The abs(ord(stack[-1]) - ord(c)) == 32 condition works because lowercase and uppercase ASCII letters differ by 32. Characters not forming a bad pair are appended to the stack, and finally, the stack contents are joined into the output string.

Go Solution

func makeGood(s string) string {
    stack := []rune{}
    for _, c := range s {
        if len(stack) > 0 && abs(int(stack[len(stack)-1]-c)) == 32 {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }
    return string(stack)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

In Go, we use a slice of runes as the stack. Each character is compared to the stack's top using the same ASCII difference check. The slice is popped by reslicing, and characters are appended normally. The abs helper function is needed because Go does not have a built-in absolute value for integers.

Worked Examples

Example 1: s = "leEeetcode"

Step	Character	Stack	Action
1	l	[l]	Push
2	e	[l,e]	Push
3	E	[l]	Pop (bad pair e-E)
4	e	[l,e]	Push
5	e	[l,e,e]	Push
6	t	[l,e,e,t]	Push
7	c	[l,e,e,t,c]	Push
8	o	[l,e,e,t,c,o]	Push
9	d	[l,e,e,t,c,o,d]	Push
10	e	[l,e,e,t,c,o,d,e]	Push

Resulting string: "leetcode"

Example 2: s = "abBAcC"

Step	Character	Stack	Action
1	a	[a]	Push
2	b	[a,b]	Push
3	B	[a]	Pop (b-B)
4	A	[]	Pop (a-A)
5	c	[c]	Push
6	C	[]	Pop (c-C)

Resulting string: ""

Example 3: s = "s"

Step	Character	Stack	Action
1	s	[s]	Push

Resulting string: "s"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is pushed and popped at most once, so linear in string length
Space	O(n)	Stack may store all characters in the worst case if no bad pairs exist

The algorithm is efficient due to the single-pass stack processing, avoiding repeated scanning.

Test Cases

# Provided examples
assert Solution().makeGood("leEeetcode") == "leetcode"  # mixed case removal
assert Solution().makeGood("abBAcC") == ""  # all removed
assert Solution().makeGood("s") == "s"  # single character

# Additional edge cases
assert Solution().makeGood("aA") == ""  # two characters removed
assert Solution().makeGood("aa") == "aa"  # same case, not removed
assert Solution().makeGood("Aa") == ""  # two characters removed
assert Solution().makeGood("abAB") == "abAB"  # no adjacent bad pair
assert Solution().makeGood("") == ""  # empty string

Test	Why
"leEeetcode"	Basic adjacent upper/lower removal
"abBAcC"	Multiple chained removals leading to empty string
"s"	Single character, already good
"aA"	Minimal removal case
"aa"	Same case, should not remove
"Aa"	Case reversal minimal removal
"abAB"	No adjacent bad pair, string remains unchanged
""	Edge case, empty input

Edge Cases

One important edge case is a string of length one. Since a single character cannot form a bad pair, it should be returned as is. Another edge case is when the string alternates perfectly between upper and lower letters, like "aAaA", which requires multiple sequential removals. The implementation correctly handles this with the stack approach because each conflict triggers a pop. A third edge case is a string with no bad pairs at all; in this case, the algorithm must not remove anything, and the stack simply accumulates all characters. This is naturally handled because the removal condition only triggers on bad pairs.