1544. Make The String Great

 

Make The String Great 

Problem Description

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

A good string is a string that doesn't have two adjacent characters s[i] and s[i + 1] where:

• 0 <= i <= s.length - 2
• 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 good, you can choose two adjacent characters that make the string bad 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.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

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

 

Constraints:

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

Approach (Using Stack)

/**
 * @param {string} s
 * @return {string}
 */
const makeGood = function (s) {
    if (s.length == 1) return s;
    let stack = [s[0]];
    for (let i = 1; i < s.length; i++) {
        if (stack.length == 0){
            stack.push(s[i]);
        }  else {
            let end = stack[stack.length - 1];
            if ((isUpperCase(end) && isLowerCase(s[i]) && isEqual(end, s[i])) || (isLowerCase(end) && isUpperCase(s[i]) && isEqual(end, s[i]))) {
                stack.pop();
                continue;
            }
            stack.push(s[i]);
        }
    }
    return stack.join("");
};


const isEqual = (s1, s2) => {
    if (s1.toLowerCase() == s2.toLowerCase()) {
        return true;
    }
    return false;
};

const isUpperCase = (character) => {
    if (character == character.toUpperCase()) {
        return true;
    }
    return false;
};

const isLowerCase = (character) => {
    if (character == character.toLowerCase()) {
        return true;
    }
    return false;
};




Complexity analysis.

Time Complexity

      We are traversing through the complete array which needs O(N).

Space Complexity

    We are using stack as extra space, hence space complexity is O(N).








Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/stack-javascript-part-1-15f9e6ebecd5




Conclusion

That’s all folks! In this post, we solved LeetCode problem #1544. Make The String Great 

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!