Consecutive character removal algorithm

Recently I came across a question in one of the coding practices quiz – Remove consecutive characters from a string and they say it as String Bomber Algorithm. I was given half an hour of time to complete the task. Looks simple at first but while writing I came across certain scenarios which proved me that the algorithm requires more thinking than anticipated. However, I  managed to complete the task in which a few test cases passed while one failed. Let us take some examples.

Examples:

Input Output
abbcd acd
abbcccd ad
abbcccad d
abbcccadag dag

Still looks simple , huh ? 🙂

The difficulty of the problem lies in re eliminating the characters which become consecutive in the output if all the characters in between them has been dropped.

Say, in example above exmple ‘abbcccad’ input should give the output as ‘d’.

Input : abbcccad

Pass 1: acccad ==> bb is consecutive so elliminated

Pass 2: aad ==> ccc is consecutive so eliminated

Pass 3: d ==> aa is consecutive so eliminated.

Hence output is ‘d’.

I wrote an algorithm which would do the above task:

package com.ds;

/**
 * Created by devashish on 2/13/2017.
 */
public class StringBomber {
    public static void main(String args[])
    {
        String input  = "abbcccadag";
        String output = "";
        char prevchar = input.charAt(0);
        for(int i  = 0 ; i < input.length()   ; )
        {

            char outputlastchar = ' ';
            if(output.length() > 0)
            {
             outputlastchar =  output.charAt(output.length()-1);
            }

            if( i == input.length() -1 )
            {
                if(outputlastchar != input.charAt(i))
                {
                    output +=input.charAt(i);
                }
                else
                {
                    if(output.length() > 0)
                    {
                        output = output.substring(0,output.length()-1);
                    }
                }
                break;
            }

            if((input.charAt(i) == input.charAt(i+1)) )
            {
                int j = i;

                while(j< input.length() && input.charAt(j) == input.charAt(i))
                {
                    j++;
                }
                i=j;
                prevchar = input.charAt(j-1);
            }
            else if(   input.charAt(i) == outputlastchar )
            {

                if(output.length() > 0)
                {
                     output = output.substring(0,output.length()-1);
                }

                prevchar = input.charAt(i);
                i++;
               
            }
            else
            {
                output +=input.charAt(i);
                prevchar = input.charAt(i);
                i++;

            }

        }

        System.out.println("output:"+output);
    }
}

 

Complexity of the above problem is O(n).

Try it and comment in case you see any issues with the algorithm.

Stay well and happy coding 🙂

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Advertisements

One thought on “Consecutive character removal algorithm

  1. Suraj

    public String bombString(String input)
    {
    int count = 0;
    int breakout = 0;
    int j ;
    int arr[] = new int[input.length()];
    while(breakout == 0)
    {
    breakout =1;
    for(int i = 0;i <= input.length()-1;i++)
    {
    arr[i]=1 ;
    for(j = i;j<input.length()-1;j++ )
    {
    if(input.charAt(i) == input.charAt(j+1) )
    {
    arr[i] += 1;
    }
    else
    {
    break;
    }
    }
    }
    for(int i =0;i = 2)
    {
    breakout = 0;
    String temp = input.substring(i,i+arr[i]);
    String t1 = input.substring(0,i);
    String t2 = input.substring(i+arr[i]);
    input = t1 + t2 ;
    break;
    }
    }
    }
    return input;
    }

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s