Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Make The String Great
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a string of English lowercase and uppercase letters, make the string "good" by removing two adjacent characters that are the same but in different cases.

Continue to do this until there are no more adjacent characters of the same letter but in different cases. An empty string is also considered "good".

Examples

Example 1

  • Input: "AaBCcdEeff"
  • Output: "Bdff"
  • Explanation: In the first step, "AaBCcDEeff" becomes "BcCDdEeff" because 'A' and 'a' are the same letter, but one is uppercase and the other is lowercase. Then we remove "cC", and "Ee". In the end we are left with "Bdff" which we can't remove - although both characters are the same but with the same case.

Example 2

  • Input: "abBA"
  • Output: ""
  • Explanation: In the first step, "abBA" becomes "aA" because 'b' and 'B' are the same letter, but one is uppercase and the other is lowercase. Then "aA" becomes "" for the same reason. The final string is empty, which is good.

Example 3

  • Input: "s"
  • Output: "s"
  • Explanation: The string "s" is already good because it only contains one character.

Constraints:

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

Solution

To solve this problem, a stack-based approach can be employed. The algorithm iterates through each character in the string. For each character, it checks if the stack is not empty and if the top element of the stack is the opposite case version of the current character (one uppercase and one lowercase of the same letter). If they are, both characters are removed; otherwise, the current character is added to the stack. This process is repeated until the end of the string. The remaining elements in the stack represent the transformed "great" string. The stack ensures that we efficiently manage the removal of adjacent characters and helps to achieve the final string in an optimized way.

Step-by-Step Algorithm

  1. Initialize an empty stack.
  2. For each character in the string from left to right:
    • If the stack is not empty and the current character and the top of the stack are the same letter but in different cases, pop the stack.
    • Otherwise, push the current character into the stack.
  3. Next, convert the stack into a string by joining all elements in the revese order.
  4. Return the final valid string.

Algorithm walkthrough

Image

  1. Initialize an Empty Stack: Begin with an empty stack.

  2. Process Each Character: Go through each character of the string one by one:

    • Character 'A': Stack is empty, so push 'A' onto the stack. Stack: ['A'].
    • Character 'a': Top of the stack is 'A', which is the uppercase version of 'a'. Pop 'A' from the stack. Stack becomes empty.
    • Character 'B': Stack is empty, so push 'B' onto the stack. Stack: ['B'].
    • Character 'C': The stack is not empty, but the top character 'B' and current character 'C' are different. So, push 'C' into the stack: ['B', 'C'].
    • Character 'c': Top of the stack is 'C', which is the uppercase version of 'c'. Pop 'C' from the stack. Stack becomes ['B'].
    • Character 'd': The top character 'B' and current character 'd' are different. So, push 'd' into the stack: ['B', 'd'].
    • Character 'E': The top character 'd' and current character 'E' are different. So, push 'd' into the stack: ['B', 'd', 'E'].
    • Character 'e': Top of the stack is 'E', which is the uppercase version of 'e'. Pop 'E' from the stack. Stack becomes ['B', 'd'].
    • Character 'f': The top character of the stack 'd' and current character 'f' are different. So, push 'f' into the stack: ['B', 'd', 'f'].
    • Character 'f': Top of the stack is 'f', but it's not the opposite case version of the current 'f'. Push 'f' onto the stack. Stack: ['B', 'd', 'f', 'f'].

  3. Resulting String: At the end of the iteration, the stack contains ['B', 'd', 'f', 'f']. The contents of the stack are then converted back to a string, which gives "Bdff" as the final output.

So, the transformed "great" string for the input "AaBbCcDdEeff" is "Bdff".

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Processing the input string: The algorithm iterates through each character in the string s. For each character, the algorithm either pushes it onto or pops it from the stack. These operations take constant time, O(1). Therefore, the total time to process the string is O(N), where N is the length of the input string.

  • Building the result string: Converting stack into the string takes O(N) time.

Overall time complexity: O(N), where N is the length of the input string.

Space Complexity

  • Stack space: The stack stores characters from the input string. In the worst case (when no characters are removed), the stack will contain all characters, which requires O(N) space.

  • Result string space: The result string is used to store the final result which also takes O(N) space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: O(N).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible