To Reduce a String

Question

I was solving a problem to reduce the form to it's non-reducible form. This was the question.

Shil has a string S , consisting of N lowercase English letters. In one operation, he can delete any pair of adjacent letters with same value. For example, string "aabcc" would become either "aab" or "bcc" after operation.

Shil wants to reduce S as much as possible. To do this, he will repeat the above operation as many times as it can be performed. Help Shil out by finding and printing 's non-reducible form!

If the final string is empty, print Empty String; otherwise, print the final non-reducible string.

Sample Input 0

aaabccddd

Sample Output 0

abd

Sample Input 1

baab

Sample Output 1

Empty String

Sample Input 2

aa

Sample Output 2

Empty String

Explanation

Sample Case 0: Shil can perform the following sequence of operations to get the final string:

Thus, we print .

Sample Case 1: Shil can perform the following sequence of operations to get the final string: aaabccddd -> abccddd

abccddd -> abddd

abddd -> abd

Thus we print abd

Sample case 1: baab -> bb

bb -> Empty String.

And what I have done till now is try to solve it through StringBuilder in Java.But some of testcases pass while other's don't and I can't find out what's the error?

Here is the code that I have tried so far.

import java.util.Scanner;

public class Solution {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    StringBuilder sb = new StringBuilder(scan.nextLine());
    for(int i = 0; i < sb.length()-1; i++)
        {
            if(sb.charAt(i) == sb.charAt(i+1))
                sb.delete(i,i+2);
                i  = 0;
        }
    if(sb.length() == 0)
        System.out.println("Empty String");
    else
        System.out.println(sb.toString());
}

}

Inputs like aaabccddd

and aa pass.But when the input is baab it fails.

Answer 1

You have to use a while loop. Problem with your code is that it just iterate through the code just one time. In first iteration though your input "baab" becomes "bb", then it checks 2nd b and try to find a "b" in i+1 (which does not exist). change your for loop to a while loop as below.

import java.util.Scanner;
public class Solution{
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    StringBuilder sb = new StringBuilder(scan.nextLine());
    int c=0;

    while(c< sb.length()-1){
        if(sb.charAt(c) == sb.charAt(c+1)){
            sb.delete(c,c+2);
            c=0;
        }
        else{
            c+=1;
        }
    }
    if(sb.length() == 0)
        System.out.println("Empty String");
    else
        System.out.println(sb.toString());
}

}