#1544

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Make The String Great

This problem requires removing adjacent characters that cancel each other out, leveraging stack-based state management.

Problem Statement

Given a string s consisting of lower and upper case English letters, a string is considered 'good' if it doesn't have any adjacent characters that cancel each other out. Two characters are said to cancel out if one is the uppercase version of the other, i.e., 'a' cancels with 'A' and 'B' cancels with 'b'.

The task is to iteratively remove such adjacent pairs from the string until no more cancellations are possible, making the string 'good'. You can pick any adjacent pair that cancels out and remove them, repeating the process until you reach a stable state.

Examples

Example 1

Input: s = "leEeetcode"

Output: "leetcode"

In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2

Input: s = "abBAcC"

Output: ""

We have many possible scenarios, and all lead to the same answer. For example: "abBAcC" --> "aAcC" --> "cC" --> "" "abBAcC" --> "abBA" --> "aA" --> ""

Example 3

Input: s = "s"

Output: "s"

Example details omitted.

Constraints

1 <= s.length <= 100
s contains only lower and upper case English letters.

Solution Approach

Use Stack to Manage State

A stack is perfect for this problem. As we iterate through the string, we push characters onto the stack. When we encounter a character that cancels with the one on top of the stack, we pop the stack. This efficiently simulates the removal of adjacent canceling characters.

Iterate Through the String

We iterate through each character of the string. For each character, check if it cancels with the character at the top of the stack. If it does, pop the stack; otherwise, push the current character onto the stack.

Build Final String from Stack

Once the iteration is complete, the stack contains the 'good' string, with no adjacent characters that cancel each other. We can then construct the final result by joining the stack's contents into a string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the length of the string, since each character is processed once. The space complexity is O(n) as well, as the stack may need to hold up to n characters in the worst case.

What Interviewers Usually Probe

Check if the candidate can recognize the stack-based nature of the problem and use it effectively.
Assess whether the candidate can iterate through the string correctly and apply stack operations.
Look for understanding of efficient space usage and time complexity analysis.

Common Pitfalls or Variants

Common pitfalls

Failing to handle case sensitivity correctly when checking for cancellations.
Not using a stack and attempting to solve the problem with other data structures that might be inefficient.
Incorrectly constructing the final result from the stack after processing the string.

Follow-up variants

Implement the same solution but track the number of cancellations performed.
Extend the problem to handle non-adjacent cancellations or more complex cancellation conditions.
Optimize the solution to handle larger strings or multiple test cases more efficiently.

FAQ

What is the main approach for solving the 'Make The String Great' problem?

The primary approach is using stack-based state management, where characters are pushed and popped from the stack based on their cancellation with adjacent characters.

Can I solve the 'Make The String Great' problem without using a stack?

While you can attempt a solution with other data structures, a stack is the most efficient and natural choice for this problem due to its ability to handle state changes in linear time.

Why is a stack used in the 'Make The String Great' problem?

A stack allows you to efficiently manage the cancellation of adjacent characters by pushing and popping elements as needed, simulating the reduction process.

How do you handle case sensitivity in this problem?

Case sensitivity is crucial in this problem. You must check if a character is the uppercase or lowercase version of the character at the top of the stack to determine if they cancel each other out.

What is the time and space complexity of the 'Make The String Great' problem?

The time complexity is O(n) because each character is processed once. The space complexity is also O(n) due to the stack that stores characters.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def makeGood(self, s: str) -> str:
        stk = []
        for c in s:
            if not stk or abs(ord(stk[-1]) - ord(c)) != 32:
                stk.append(c)
            else:
                stk.pop()
        return "".join(stk)

Continue Practicing

#1541 minimum insertions to balance a parentheses string #1598 crawler log folder #1614 maximum nesting depth of the parentheses