Make The String Great Leetcode Solution

Problem Statement

In “Make The String Great” problem a string is given consists of lower and upper case letters. We have to make this string good by removing adjacent characters in the string which is making the string bad.
A good string is a string which doesn’t have two adjacent characters where both the characters are same but of different case. We can do this operation any number of times to make the string good.

Example

s = "leEeetcode"

"leetcode"

Explanation:

In the first step, we can choose index 1 and 2 or 2 and 3,  both will reduce “leEeetcode”  to “leetcode”.

"abBAcC"

""

Explanation:

Possible scenarios are :

Approach

The given String has some adjacent character which are same but in opposite case. So What we have to do is whenever we encounter these two characters we have to remove both of them and again repeat the process for the remaining string.

For this what we can do is that we can iterate from the first character of the given string and append the character to our result string untill it is not bad.
Before appending the current character we would check if appending this character to res string would make it bad or not by comparing it with the last character of res string. If integral difference (ascii) between those two characters is equal to 32 then it is bad combination otherwise it is good. On the basis of that we will do following operation:

• if appending the character will not make bad, we would just simply append that character to res.
• Else, we would not append and will remove the last character of res string.

For the above algorithm we can use stack data structure for pushing character to the end and popping out character from the end.
In C++ we can also use string class as a stack of characters and can use push_back() and pop_back() operations like stack class.

Implementation

C++ Program for Make The String Great Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

string makeGood(string s) {

    string goodString;

    for(char ch:s)
    {
        if((!goodString.empty()) && abs(goodString.back()-ch)==32)  
            goodString.pop_back();
        else  
            goodString.push_back(ch);
    }

    return goodString;
}

int main() 
{
    string s = "leEeetcode";
    
    cout<<makeGood(s)<<endl;

  return 0; 
}

"leetcode"

Java Program for Make The String Great Leetcode Solution

import java.lang.*;
import java.util.*;

class Rextester
{  
    public static String makeGood(String s) {

        Stack<Character> stack= new Stack<Character>();

        for(int i=0;i<s.length();i++)
        {
            if((!stack.isEmpty()) && Math.abs(stack.peek()-s.charAt(i))==32 )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        char res[]= new char[stack.size()];
        
        for(int i=res.length-1;i>=0;i--) 
            res[i]= stack.pop();

        return new String(res);

    }
    
    public static void main(String args[])
    {
        String s = "leEeetcode";

        System.out.println(makeGood(s));
        
    }
}

"leetcode"

Complexity Analysis for Make The String Great Leetcode Solution

Time Complexity

O(n) : Where n is the length of the input string. Because we are iterating through the string in a single loop. Hence time complexity will be order of n.

Space Complexity 

O(n) : We are using a stack to store our final result. Hence space used will be order of n, i.e. O(n).