LeetCode #1544 Make The String Great Solution & Explanation

Content

Post Views: 133

LeetCode Problem

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

A good string is a string which 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.

Solution

In our initial approach, we used a combination of while and for loops to iteratively check the string. We aimed to remove adjacent characters that had the same letter but different cases until the string became “good”.

C# Solution

⚠️Solution1

public class Solution {
    public string MakeGood(string s) {
        
        while(s.Length>1){
            var len = s.Length-1;
            for(int i=0; i<len;i++){
                if(s[i]!=s[i+1] && (char.ToUpper(s[i]) == s[i+1] || char.ToLower(s[i]) == s[i+1])){
                    s = s.Remove(i,2);
                    break;
                }

                if(i==len-1){
                    return s;
                }
            }
        }
        return s;
    }
}

After submitting this solution, we identified several areas where further improvements could be made.

Solution2 – using StringBuilder

public class Solution {
    public string MakeGood(string s) {
        StringBuilder sb = new StringBuilder(s);

        while(sb.Length>1){
            var len = sb.Length-1;
            for(int i=0; i<len;i++){
                if(char.ToUpper(sb[i]) == char.ToUpper(sb[i+1])){
                    if((char.IsUpper(sb[i])&&char.IsLower(sb[i+1])) || (char.IsLower(sb[i])&&char.IsUpper(sb[i+1]))){
                        sb.Remove(i,2);
                        break;
                    }
                }

                if(i==len-1){
                    return sb.ToString();
                }
            }
        }
        return sb.ToString();
    }
}

This is our second solution. There are two improvements:

Firstly, we used StringBuilder to reduce performance overhead from redundant string definitions.
Secondly, we optimized the condition by splitting:
- before : if(s[i]!=s[i+1] && (char.ToUpper(s[i]) == s[i+1] || char.ToLower(s[i]) == s[i+1]))
- after : if(char.ToUpper(sb[i]) == char.ToUpper(sb[i+1])) + if((char.IsUpper(sb[i])&&char.IsLower(sb[i+1])) || (char.IsLower(sb[i])&&char.IsUpper(sb[i+1])))

This optimization ensures that the additional case-insensitive checks are performed only when two characters have the same letter, thereby reducing unnecessary computations.

Java Solution

Solution1

class Solution {
    public String makeGood(String s) {
        StringBuilder sb = new StringBuilder(s);

        while (sb.length() > 1) {
            int len = sb.length() - 1;
            for (int i = 0; i < len; i++) {
                if (Character.toUpperCase(sb.charAt(i)) == Character.toUpperCase(sb.charAt(i + 1))) {
                    if ((Character.isUpperCase(sb.charAt(i)) && Character.isLowerCase(sb.charAt(i + 1))) ||
                            (Character.isLowerCase(sb.charAt(i)) && Character.isUpperCase(sb.charAt(i + 1)))) {
                        sb.delete(i, i + 2);
                        break;
                    }
                }

                if (i == len - 1) {
                    return sb.toString();
                }
            }
        }

        return sb.toString();
    }
}

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Make The String Great – LeetCode

Some Random LeetCode posts

LeetCode Problem

Solution

C# Solution

Java Solution

Conclusion

LeetCode #278 First Bad Version Solution & Explanation

LeetCode #122 Best Time to Buy and Sell Stock II Solution & Explanation

LeetCode #2966 Divide Array Into Arrays With Max Difference Solution & Explanation

LeetCode #389 Find the Difference Solution & Explanation

LeetCode #168 Excel Sheet Column Title Solution & Explanation

LeetCode #881 Boats to Save People Solution & Explanation

Leave a ReplyCancel Reply

LeetCode Problem

Solution

C# Solution

Java Solution

Conclusion

Related Posts

Leave a ReplyCancel Reply