Recursively remove all adjacent duplicates Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/recursively-remove-all-adjacent-duplicates0744/1

(It is also the problem of the day for 21-04-2022)

Solution:

class Solution{

    String remove(String s) {

        boolean flag=false;

        for(int i=0;i<s.length()-1;i++){

            if(s.charAt(i)==s.charAt(i+1)){

                flag=true;

                break;

            }

        }

        if(flag!=true){

            return s;

            

        }

        else{

            StringBuilder sb1=new StringBuilder(s);

            StringBuilder sb=new StringBuilder();

            sb1.append('0');

            String s1=sb1.toString();

            //System.out.println(s1);

            char c=s1.charAt(0);

            int count=1;

            

            for(int i=1;i<s1.length();i++){

                if(s1.charAt(i)!=c){

                    if(count==1){

                        sb.append(c);

                    }

                    else{

                        count=1;

                    }

                    c=s1.charAt(i);

                }

                else{

                    count++;

                }

            }

            

            return remove(sb.toString());

        }

       

    }

}

Time Complexity:O(String Length*duplicates count)[GFG Time:0.52/2.77].Basically, no accurate time complexity can be predicted but yes >=O(String Length) [String Length is also dynamic and change after every iteration.]

Best Case: When the string consists of all duplicates. One-time traversal and return string as output.

Space Complexity: O(1)

Auxiliary Space: O(String Length)[StringBuilder of equivalent or smaller size than an actual string is used.]

Total Test Cases:358

Approach Used:

Here we need to remove all the adjacent duplicates and we need to repeat it till the string is of unique characters only.

So breaking this approach into two subparts

1. Do it first for one time.

2. Do it till all the duplicates are removed.

Now the question arises of how we will know that is there any duplicate present in the string or not.

For that we will traverse the string and check for duplicates moreover we will also have a flag that will point to false and if it becomes true then it means a duplicate is there.

So every time we will also maintain a check on the flag also, if that becomes false we will return the string otherwise we will recursively call the same function with a modified string.

Now for string traversal, we have to remove duplicates so keeping that in mind we will use the approach

1. char c pointing to the first character of the string.

2. traverse loop from i=1 to string length and see whether the incoming character is equal to c or not.

    If it is equal to c then we will increase the count

    If it is not then we will check for the count value.

            if the count is 1 it means the character appears only for one time and hence it is unique. So appending unique character in StringBuilder object.

            else we will make count as 1(it means change is there but the element had frequency more than 1 ie duplicates.)

3. The StringBuilder object in which we are appending characters we will return as a new modified string.

The point to be noted here is I appended 0 as a character at end of the string.

It is so because while traversing you will be comparing all the characters and either add them in StringBuilder or not but the last character will be left unadded or discarded depending on its frequency. So for that only I have added 0 in the last so that the actual last character will be checked and added or discarded according to its frequency.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"