algoadvance

Leetcode 1544. Make The String Great

Problem Statement:

Given a string s of lower and upper case English letters.

A string is considered “great” if there are no two adjacent characters s[i] and s[i + 1] where:

• s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice versa.

To make the string great, you can choose two adjacent characters that make the string not great and remove them.

Repeat this process until you make the string great.

Return the resulting string. It is guaranteed that the answer is unique under the given constraints.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, remove "eE", then "leEeetcode" becomes "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: Remove "abBA", then the string becomes "cC", then remove "cC", so the final string is empty.

Example 3:

Input: s = "s"
Output: "s"

Clarifying Questions:

1. Can the input string be empty?
   • Yes, the input string can be empty.
2. What is the length of the input string s?
   • The length of the input string s can be up to 100.

Strategy:

We can use a stack to process the string. The idea is to traverse the string character by character and use the stack to keep track of the characters we’ve seen.

• Initialize an empty stack.
• Iterate through characters in the string s.
• For each character, check if the stack is not empty and the character at the top of stack is the opposite case of the current character.
  • If both the conditions satisfy, pop the character from the stack (it means we are removing both characters as they cancel out each other).
  • If not, push the current character onto the stack.
• After processing all characters, the stack will contain the resultant “great” string.
• Convert the stack back to a string and return it.

Code:

public class Solution {
    public String makeGood(String s) {
        StringBuilder stack = new StringBuilder();
        for (char ch : s.toCharArray()) {
            int size = stack.length();
            if (size > 0 && 
                Math.abs(stack.charAt(size - 1) - ch) == 32) {
                stack.deleteCharAt(size - 1);
            } else {
                stack.append(ch);
            }
        }
        return stack.toString();
    }
}

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the string s. This is because we are processing each character of the string exactly once.

The space complexity is also O(n) in the worst case if no characters are removed, and all characters are stored in the stack.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?