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.

I ran your program and it seems to be printing output as "bb" for your input string "baab" — mhasan, Oct 06 '16 at 04:30
It is a _challenge_, but here's a solution from github https://www.hackerrank.com/challenges/reduced-string and https://github.com/shengmin/coding-problem/tree/master/hackerrank/string-reduction — Nick Bell, Oct 06 '16 at 04:31
I am solving the challenge from there itself.But I don't want to see the solution.I need to know if I can solve by this method which i am trying and if so what am I doing wrong? — john400, Oct 06 '16 at 04:50

Vũ Đức Quý · Answer 1 · 2016-10-06T04:57:48.843

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();
}
}

Your code just right when the string has only one reducible substring. — Vũ Đức Quý, Oct 06 '16 at 04:59
Hey the code is working fine.But let me just understand how it's working.Thank you very much though..:) — john400, Oct 06 '16 at 05:08

Dimuth Tharaka Menikgama · Accepted Answer · 2016-10-06T05:32:30.823

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());
}

}

edited Oct 06 '16 at 05:32

answered Oct 06 '16 at 04:49

Dimuth Tharaka Menikgama

122
1
9

I have edited the code and added i =0 in the loop so that it checks the first b again.Can you check it?If that could be a valid process? – john400 Oct 06 '16 at 05:02
Sure I will check that. please give me a moment. – Dimuth Tharaka Menikgama Oct 06 '16 at 05:07
You are welcome. According to this post it is too confusing to change index inside for loop. So it is better if you use while loop for that. [link](http://stackoverflow.com/questions/30088401/change-index-inside-a-for-loop) . . – Dimuth Tharaka Menikgama Oct 06 '16 at 05:16
Ok, one thing why did you use "change" variable here? I just couldn't understand it's use. – john400 Oct 06 '16 at 05:20
That can be removed. I changed that in the answer. – Dimuth Tharaka Menikgama Oct 06 '16 at 05:35

score 0 · Answer 3 · answered Oct 06 '16 at 05:15

you can do with the help of lable try this,

 public static void main(String[] args) {
     boolean canReduce = true;
     Scanner scan = new Scanner(System.in);
     StringBuilder sb = new StringBuilder(scan.nextLine());


     startPoint: while (sb.length() > 0 && canReduce) {
        for (int i = 0; i < sb.length() - 1; i++) {
            if (sb.charAt(i) == sb.charAt(i + 1)) {
                sb.delete(i, i + 2);
                canReduce=true;
                 continue startPoint;
            }else{
                canReduce=false;
            }

        }
    }

    if (sb.length() == 0) {

        System.out.println("Empty String");
    } else {

        System.out.println(sb.toString());
    }
}

score 0 · Answer 4 · answered Mar 30 '17 at 03:05

Try this:

    public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    StringBuilder sb =new StringBuilder(in.nextLine());

   for (int i=0; i<sb.length()-1; i++){
        if(sb.charAt(i)==sb.charAt(i+1)){
            sb.delete(i, i+2);
            i=-1;

     }
    }
    if(sb.length()==0){
        System.out.println("Empty String");
    }else{
        System.out.println(sb);
    }
   }

To Reduce a String

4 Answers4