Tag Archives: string dropping

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 🙂