algoadvance

Leetcode 1544. Make The String Great

Problem Statement

The problem is defined as follows:

1544. Make The String Great

Given a string s of lower and upper case English letters, a good string is a string where no two adjacent characters are the same letter with different cases.

For example, “leEeetcode” is not good because ‘e’ and ‘E’ are adjacent to each other, but “leetcode” and “leEeetcode” is not good because ‘e’ and ‘E’ are adjacent to each other. However, “leetcode” is a good string because it does not have two adjacent characters that are the same letter with different cases.

To make the string good, you can choose two adjacent characters that make the string not good and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Clarifying Questions

  1. What characters are considered “same letters with different cases”?
    • Characters like ‘a’ and ‘A’, ‘b’ and ‘B’, etc.
  2. Can the input string be empty?
    • Yes, and if it is empty, the output should also be an empty string.
  3. Is the input string limited to alphabetic characters only?
    • Yes, the input string consists of only alphabetical characters, both lowercase and uppercase.

Example

Input: s = "leEeetcode"
Output: "leetcode"

Strategy

A feasible strategy for this problem is to use a stack to handle the removals of problematic adjacent characters. The key idea is to iterate through the string:

  1. If the stack is empty, push the current character onto the stack.
  2. If the stack is not empty, check the top character of the stack and compare it with the current character:
    • If they form a “bad” pair (one is uppercase and the other is lowercase of the same letter), pop the top character off the stack.
    • Otherwise, push the current character onto the stack.
  3. Convert the contents of the stack into the resulting string.

Code Implementation

Here’s the C++ solution for the problem:

#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

string makeGood(string s) {
    // Use a stack to help in removing bad adjacent pairs
    stack<char> st;
    
    for (char ch : s) {
        if (!st.empty() && abs(st.top() - ch) == 32) { // 32 is the difference between lowercase and uppercase alphabet
            st.pop();
        } else {
            st.push(ch);
        }
    }
    
    // Construct the resulting string from the stack
    string result = "";
    while (!st.empty()) {
        result = st.top() + result;
        st.pop();
    }
    
    return result;
}

// Test code
int main() {
    string s = "leEeetcode";
    cout << "Output: " << makeGood(s) << endl;  // Output should be "leetcode"
    return 0;
}

Time Complexity

Therefore, the overall time complexity is O(n), which is efficient for this problem.

Space Complexity

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