Daily Question – 1544. Make The String Great

Description: https://leetcode.com/problems/make-the-string-great/description/?envType=daily-question&envId=2024-04-05

Note:

One direct way is to continue iterating the array until no “bad pair” exists.

Code (Time complexity is O(n2) )

class Solution {
    public String makeGood(String s) {
        char[] chars = s.toCharArray();
        int x = 0,y = 0;
        boolean h = true;
        StringBuilder sb = new StringBuilder();
        while (h) {
            h = false;
            for (int i = 1; i < s.length(); i++) {
                if (Character.isUpperCase(chars[i])) x = (int) 'A' - (int) chars[i]; else x = (int) chars[i] - (int) 'a';
                if (Character.isUpperCase(chars[i-1])) y = (int) 'A' - (int) chars[i-1]; else y = (int) chars[i-1] - (int) 'a';
                if (x + y == 0 && !(chars[i] == 'a' && chars[i-1]=='a') && !(chars[i] == 'A' && chars[i-1]=='A')) {
                    chars[i] = '0';
                    chars[i-1] = '0';
                    h = true;
                }
            }
            sb.delete(0,sb.length());
            for (char c : chars) {
                if (c != '0') sb.append(c);
            }
            s = sb.toString();
            chars = s.toCharArray();
        }
        return s;
    }
}

Improvement:

1. Initialize an empty stack.
2. Iterate through each character in the input string.
3. For each character, check if it forms a bad pair with the top character of the stack. If it does, pop the character from the stack.
4. If the character doesn’t form a bad pair, push it onto the stack.
5. Finally, join the characters left in the stack to form the resultant string.

code:

class Solution {
    public String makeGood(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && Math.abs(c - stack.peek()) == 32) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.insert(0, stack.pop());
        }
        
        return result.toString();
    }
}