< Back




1544. Make the String Great

Omit duplicates in a string where the duplicates are adjacent and they differ by case - lower and
upper. Inuitively solved with a stack to maintain the last seen character. If the stack contains
characters, compare the top of the stack with the current character, using an XOR trick to calculate
the difference. If the difference is 32, pop the stack. Otherwise, append the character to the stack.

The solution is as follows:


  class Solution:
      def makeGood(self, s: str) -> str:
          stack = []

          for c in s:
              if stack and ord(c) ^ ord(stack[-1]) == 32:
                  stack.pop()
              else:
                  stack.append(c)


          return "".join(stack)


_ Time Complexity:

  O(n) - We inspect all characters within the string.

_ Space Complexity:

  O(n) - We maintain a stack of only unique characters.