💬 Discord
Sign In
NeetCode #349LC-1544EasyStack
← Back to All Problems

#349 · #1544 · Make The String Great(整理字符串)

📌 Problem Statement & Constraints

Given a string s of lower and upper case English letters, a string is great if no two adjacent characters are the same letter in different cases. Repeatedly remove such pairs until none remain, and return the result. Constraints: 1 <= s.length <= 100.

💡 Core Algorithmic Approaches

  1. A stack processes the string left to right. The only removals possible are between the current character and the stack top.
  2. If the top and the current character are the same letter with different cases, they cancel and the top is popped.
  3. Otherwise push the character. A removal can expose a new cancelling pair, but the loop handles that automatically because the next character is compared against the new top.
  4. The result is the stack joined.

💻 Benchmark Python3 Implementation

class Solution:
    def makeGood(self, s: str) -> str:
        st = []
        for ch in s:
            # same letter, different case -> they cancel
            if st and st[-1] != ch and st[-1].lower() == ch.lower():
                st.pop()
            else:
                st.append(ch)
        return "".join(st)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is pushed or popped once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing st[-1].lower() == ch.lower() without the case check: equal letters in the same case must not cancel, so st[-1] != ch is required.
  • Using a while loop to rescan after a removal: unnecessary -- the stack top is already the new neighbour.
  • Comparing with st[-1].upper() == ch.upper(): that is equivalent for letters but confusing; lower() is conventional.
  • Trying to rebuild the string in place: the stack approach is cleaner and equally efficient.