How do you solve Make The String Great on LeetCode?

Make The String Great (LeetCode #1544) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a stack allows us to handle adjacent pairs efficiently.

What is the brute force solution for Make The String Great?

The brute force approach for Make The String Great is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves repeatedly scanning the string to find and remove adjacent bad pairs until no more can be removed. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Make The String Great?

Make The String Great uses the following concepts: String, Stack. The recommended patterns to study are: Stack, Greedy.

What are the interview tips for Make The String Great?

Always think about using a stack for problems involving sequences and pairs. Explain your thought process clearly while coding; it helps the interviewer understand your approach. Consider edge cases, such as strings that are already good or those that can become empty.

What are common mistakes when solving Make The String Great?

Not checking for empty stack before popping, which can lead to runtime errors. Overcomplicating the logic instead of using a simple stack mechanism.

#1544

Make The String Great

Easy

StringStackStackGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a stack allows us to efficiently manage the characters and remove bad pairs in a single pass through the string. This approach is much faster than the brute-force method.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty stack.
2Step 2: Iterate through each character in the string.
3Step 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. If so, pop the stack (remove the bad pair).
4Step 4: If not, push the current character onto the stack.
5Step 5: At the end, convert the stack back to a string.

solution.py8 lines

1def makeGood(s):
2    stack = []
3    for char in s:
4        if stack and abs(ord(stack[-1]) - ord(char)) == 32:
5            stack.pop()  # Remove the bad pair
6        else:
7            stack.append(char)
8    return ''.join(stack)

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once, and the space complexity is O(n) due to the stack potentially holding all characters in the worst case.

1Using a stack allows us to handle adjacent pairs efficiently.
2The character comparison using ASCII values simplifies the detection of bad pairs.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.