easy Problem 9 Make The String Great

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

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:

import java.util.Stack;

public class Solution {

  public String makeGood(String s) {
    // Create a stack to store characters.
    Stack<Character> stack = new Stack<>();

    // Iterate through each character in the input string.
    for (char c : s.toCharArray()) {
      // Check if the stack is not empty and the current character (ignoring case)
      // is equal to the character at the top of the stack (ignoring case), but they
      // are of different cases (e.g., 'a' and 'A', or 'b' and 'B').
      if (
        !stack.empty() &&
        Character.toLowerCase(stack.peek()) == Character.toLowerCase(c) &&
        !stack.peek().equals(c)
      ) {
        // If the conditions are met, pop the character from the stack,
        // effectively removing the pair of characters.
        stack.pop();
      } else {
        // If the conditions are not met, push the current character onto the stack.
        stack.push(c);
      }
    }

    // Create a StringBuilder to construct the final result.
    StringBuilder sb = new StringBuilder();

    // Iterate through the characters remaining in the stack and append them to the StringBuilder.
    for (char c : stack) {
      sb.append(c);
    }

    // Convert the StringBuilder to a string and return the result.
    return sb.toString();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.makeGood("AaBCcdEeff")); // Output: "Bdff"
    System.out.println(solution.makeGood("abBA")); // Output: ""
    System.out.println(solution.makeGood("s")); // Output: "s"
  }
}

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, . Therefore, the total time to process the string is , where N is the length of the input string.

• Building the result string: Converting stack into the string takes time.

Overall time complexity: , 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 space.

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

Overall space complexity: .