Question

Remove all consecutive duplicates from the string in java.

Answer 1

Here, we will see the solution in iterative way. The process is to keep track of two indexes, index of current character in str and index of next distinct character in str. Whenever we see same character, we increment only current character index. When we see the different character, we increment the index of distinct character.

This iterative way solution will take O(n) as time complexity.

See the following code to remove all consecutive duplicates from the string:- 

public class RemovingConsecutiveDuplicates {

public static void main(String[] args) {

String str = "aaaaaabaabccccccc";

System.out.println(removeConsecutiveDuplicatesFromString(str.toCharArray()));

}

// Iterative function that removes consecutive duplicates from string

//Time Complexity : O(n)

//Auxiliary Space : O(1)

    public static String removeConsecutiveDuplicatesFromString(char[] ch){ 

        int n = ch.length; 

        // We don't need to do anything for empty or single character string. 

        if (n < 2) { 

            return null; 

        } 

  

        // j is used to store index is result string (or index of current distinct character)  

        int j = 0; 

        // Traversing string  

        for (int i = 1; i < n; i++){ 

            // If current character ch[i] is different from ch[j] 

            if (ch[j] != ch[i]) { 

                j++; 

                ch[j] = ch[i]; 

            } 

        } 

        ch = Arrays.copyOfRange(ch, 0, j + 1);

        return new String(ch); 

    } 

}

Input:- "aaaaaabaabccccccc";

Output:- ababc

Answer 2

See the bellow solution to remove all consecutive duplicates from the given string. Here, we use stack data structure . 

See the code to remove all consecutive duplicates from string:- 

public class RemovingConsecutiveDuplicates {

public static void main(String[] args) {

String str = "aaaaaabaabccccccc";

System.out.println(removeConsecutiveDuplicates(str));

}

//Time Complexity O(n)

       // Space Complexity O(n) where n is distinct consecutive characters

public static String removeConsecutiveDuplicates(String str){

        StringBuilder sb = new StringBuilder();

        Stack<Character> stack = new Stack<>();

        for(int i=0; i<str.length(); i++){

            if(stack.isEmpty() || stack.peek() != str.charAt(i)){

                stack.push(str.charAt(i));

                sb.append(str.charAt(i));

            }

        }

        return sb.toString();

    }

}

Input:- aaaaaabaabccccccc

Output:-ababc