Remove consecutive duplicate characters from the given string

Given a string, remove consecutive duplicate characters from the given string. The output should not have any duplicate characters. For Examples: If the given string is "abcccbd" algorithm should first remove "ccc" and then "bb", so the final string will become "ad". The algorithm should destroy the characters only if there are more than 1 continuous occurrence of same character in the string. This algorithm call Marquez Algorithm.

        Examples:
        Input 1: aabccdee
        Output: bd

        Explanation->
        Step 1: aabccdee
        Step 2: bccdee
        Step 3: bdee
        Step 4: bd(Final Answer)

        Input 2: abcdeedcbfgf
        output: afgf

        Explanation->
        Step 1: abcdeedcbfgf
        Step 2: abcddcbfgf
        Step 3: abccbfgf
        Step 4: abbfgf
        Step 5: afgf(Final Answer)

        Input 3: abbabba
        Output: a

        Explanation:
        Step 1: abbabba
        Step 2: aabba
        Step 3: bba
        Step 4:a(Final Answer)

        Input 4: aa
        Output: (Empty string)

        Explanation:
        Step 1: aa
        Step 2:
    

A simple approach would be to run the input string through multiple passes. In every pass remove all the consecutive duplicate characters from left to right. Stop running when pass does not have any duplicate.

Below is java program.

package com.walking.techie.data.structure.string;


public class MarquezAlgo {

  private static int step = 1;

  public static void main(String[] args) {
    MarquezAlgo obj = new MarquezAlgo();
    String input1 = "aabccdee";
    obj.removeConsecutiveCharacters(input1);
    System.out.println();
    step = 1;

    String input2 = "abcdeedcbfgf";
    obj.removeConsecutiveCharacters(input2);
    System.out.println();
    step = 1;

    String input3 = "abbabba";
    obj.removeConsecutiveCharacters(input3);
    System.out.println();
    step = 1;

    String input4 = "aaaa";
    obj.removeConsecutiveCharacters(input4);
    System.out.println();
    step = 1;

    String input5 = "abcdef";
    obj.removeConsecutiveCharacters(input5);
  }

  private String removeConsecutiveCharacters(String input) {
    if (input == null) {
      return input;
    }
    // input size is 1
    if (input.length() == 1) {
      return input;
    }

    /* check on every step input contain
    * adjacent duplicate characters
    */
    while (isValid(input)) {
      int length = input.length(); //length of input string
      int firstIndex = 0;
      boolean findConsecutiveDuplicates = false;
      int i;

      //start from the second character
      for (i = 1; i < length; i++) {
        // firstIndex will find consecutive duplicate characters from index 0 to i
        if (input.charAt(i) == input.charAt(i - 1)) {
          findConsecutiveDuplicates = true;
          firstIndex = i + 1;
        } else {
          // find string then break the for loop
          if (findConsecutiveDuplicates) {
            input = input.substring(firstIndex);
            break;
          }

          // find consecutive duplicate characters in between 0 to length-1
          int prev = i - 1;
          StringBuilder sb = new StringBuilder();
          while (i < length) {
            if (!findConsecutiveDuplicates && input.charAt(prev) != input.charAt(i)) {
              sb.append(input.charAt(prev));
              prev = i;
            } else {
              findConsecutiveDuplicates = true;
              if (findConsecutiveDuplicates && input.charAt(prev) != input.charAt(i)) {
                sb.append(input.substring(i));
                break;
              }
            }
            i++;
          }
          // if no consecutive duplicate character found, then add the last character of input string
          if (!findConsecutiveDuplicates) {
            sb.append(input.charAt(i - 1));
          }
          // assign string back to input
          input = sb.toString();
          break;
        }
      }
      // to handle case like aa, aaaaa
      if (i == input.length()) {
        input = input.substring(firstIndex);
      }
    }
    return input;
  }

  // This method validates string contain consecutive characters
  private boolean isValid(String string) {
    System.out.println("Step " + step++ + " " + string);
    for (int i = 1; i < string.length(); i++) {
      if (string.charAt(i - 1) == string.charAt(i)) {
        return true;
      }
    }
    return false;
  }
}

Output of above program is shown below:

Step 1 aabccdee
Step 2 bccdee
Step 3 bdee
Step 4 bd

Step 1 abcdeedcbfgf
Step 2 abcddcbfgf
Step 3 abccbfgf
Step 4 abbfgf
Step 5 afgf

Step 1 abbabba
Step 2 aabba
Step 3 bba
Step 4 a

Step 1 aaaa
Step 2

Step 1 abcdef