Make the String Great — Stack Same-Letter Case Check

Problem 259 · Make the String Great

Difficulty: Easy · Pattern: Stack + Adjacent Pair Removal

Remove pairs of adjacent characters that are the same letter but different case.

Solutions

# Python
def makeGood(s):
    stack = []
    for c in s:
        if stack and stack[-1] != c and stack[-1].lower() == c.lower():
            stack.pop()
        else:
            stack.append(c)
    return ''.join(stack)

// Java
public String makeGood(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek()!=c && Character.toLowerCase(stack.peek())==Character.toLowerCase(c))
            stack.pop();
        else stack.push(c);
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.reverse().toString();
}

Complexity

Time: O(n)
Space: O(n)