john400 john400 - 1 month ago 22
Java Question

To Reduce a String

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.Can anyone please help me?Thanks in advacnce.

Answer

The problem is you just run loop through the string for one time. For example: String "baab", you just delete "aa" and finish the loop.

Solution: use recursion with a flag isNonReducible, loop until it give empty string or flag isNonReducible = true;

public class Solution {
public static StringBuilder checkReducible(StringBuilder sb) {
    boolean isNonReducible = true;
    for (int i = 0; i < sb.length() - 1; i++) {
        if (sb.charAt(i) == sb.charAt(i + 1)) {
            isNonReducible = false;
            sb.delete(i, i + 2);    
        }
    }
    if (sb.length() == 0) {
        return new StringBuilder("Empty String");
    }
    else {
        if(!isNonReducible) {
            sb = checkReducible(sb);
        }
        return sb; 
    }
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    StringBuilder sb = new StringBuilder(scan.nextLine());
    System.out.println(checkReducible(sb));
    scan.close();
}
}
Comments