How to Remove all adjacent duplicates characters from String in java? Example Tutorial

Hello guys, if you are wondering how to remove adjacent repeated characters or duplicates from a given String in Java then you have come to the right place. In the last article, we have seen how to find duplicate characters as well as how to remove duplicate characters from String in Java, and in this article, we will take that topic to another level and remove adjacent duplicates from given String. This topic gives another perspective to removing duplicates in a word or phrase. Probably before now, you are familiar with removing duplicates from a word or phrase, or number. But this topic gives a detailed understanding of how to remove adjacent duplicates. 

If you are wondering what is the meaning of adjacent duplicate then don't worry. This means duplicates that are next to each other for example: let’s say you have the word “Marry”, by the time you write your code implementation the output should print “Mary”. Another one is “Anniversary” one n is removed too hence why we have “Aniversary”.

Given a set of Strings or int, we would remove all adjacent duplicates,(right now we are focusing on strings) meaning if there is are characters that are the same and are adjacent(I.e) next to each other- we are going to remove it.

For instance, let’s say we have the word “anniversary”, removing adjacent duplicate means removing one n in the anniversary. There are two n close to each other and anywhere in the phrase where there is the same letter rightly placed beside each other it should remove one.



Java Program to remove All Adjacent Repeated Characters from String

Now that you know what does it mean by removing adjacent duplicate characters from a given String, it's time to see the code.  

Here is the implementation for it for better understanding:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class AdjacentDuplicate {
    public String removeDuplicates(String string) {
        if (string == null) {
            return null;
        }
        char[] chars = string.toCharArray();
        char previous = ' ';
        int i = 0;
        for (char c: chars) {
            if (c != previous) {
                chars[i++] = c;
                previous = c;
            }
        }
        return new String(chars).substring(0, i);
    }
    public static void main(String[] args) {
        AdjacentDuplicate adj = new AdjacentDuplicate();
        String string1 = "aabaarbarccrabmq";
        String string2 = "marry";
        System.out.println(adj.removeDuplicates(string1));
        System.out.println(adj.removeDuplicates(string2));
    }
}

Now, let's see the explanation of our solution and this program to understand the solution in a bit more detail and know how this code is working, and remove adjacent duplicate characters from the input string. 




EXPLANATION

Line 1 was the class declaration followed by method declaration removeDuplicate() in line 2, which takes in a string of type String as a parameter. If the String is null then it returns null but if not the program proceeds to line 6 to convert the string to char array and stores it in a char array variable. 

The variable previous of type char was initialized to an empty string, it could be any singular letter or symbol.

Note: char is with a single quote while String is in double quote. They are also known as char literal and string literal as explained in this article. 

The counter i was initialized to 0 in line 8. and there is an iteration in line 9 that goes through each character in the char array, so if any of the characters are not equal to the previous, then c is assigned value at i as it increments to the next. After that previous is been reset to c.

Then line 15 returns a new String of the char array, with its substring as specified from the starting and ending point in the parenthesis. Line 17 is the main method, line 18 creates the instance of the class “Adjacent Duplicate”.

The input was passed to the variable string1 of type String and string2 as well in lines 19 and 20. In Line 21 and 22, the method removeDuplicates() was called and printed out respectively.


OUTPUT:

abarbarcrabmq

Mary


You can see that the output doesn't have any adjacent duplicate characters anymore, they were removed by our code.




Recursive Algorithm to remove all adjacent duplicate characters from String

You can as well use the recursion method to solve this problem. You just need to understand what is recursion first. Recursion is a basic programming technique you can use in Java, in which a method calls itself to solve some problem. 

A method that uses this technique is called the recursive method. The end condition indicates when the recursive method should stop calling itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

Let’s check the code implementation in a recursive way.


1
2
3
4
5
6
7
8
public String removeDuplicates(String word, int number) {
        for (int i = 1, count = 1; i < word.length(); i++) {
            count = word.charAt(i) == word.charAt(i-1) ? count + 1 : 1;
        if (count == number)
           word = removeDuplicates(word.substring(0, i-number+1) 
                 + word.substring(i+1), number);
        }
        return word;
    }


The method in a recursive way is a bit different in the sense that, the input from which we want to remove the adjacent duplicates is not only what was passed in the method, there is another parameter of type int and whatever the argument is.

For example, 3, means that you are removing any three letters that are adjacent to one another and because it is a recursive method that keeps calling itself, it keeps removing any three letters that are adjacent until there are no more. 


Now let’s go to the explanation of the Recursion.

 Line 1 declared the method removeDuplicates() that returns strings eventually. It takes in two parameters. The first one is of type string which is what we want to eliminate adjacent duplicates from. And the second parameter is an integer. In line 2 there is a for loop. The count in the for loop is to keep track and store each character in the string at different running.

So if the condition in line 3 is true it returns the count and increments it, else it returns 1. Now, here is the recursion part, in line 4. if the count is equal to the number the method removeDuplicates() would be called, with the substring of the word with the right argument, and the other argument which is the number.

Input:

aaabdddc

Output:

bc



That's all about how to remove adjacent duplicate characters from a given String in Java. As I said, this is an interesting problem and pattern to know and there are many variations of this problem like just removing duplicates from a given String or sometimes just finding and printing duplicates instead of printing them. 

Since String is an important data structure and one of the important topics for coding interviews, practicing as many String problems will give you an edge over other candidates and also help you to become a better programmer. 


Other String Coding Problems for Practice 
  • 21 String coding problems for Java developers (questions)
  • How to convert a numeric string to an int? (solution)
  • How to check if a string contains only digits?  (solution)
  • How to Print duplicate characters from String? (solution)
  • How to program to print the first non-repeated character from String? (solution)
  • How to check if two Strings are anagrams of each other? (solution)
  • How to check if String is Palindrome? (solution)
  • How to count the number of vowels and consonants in a String? (solution)
  • How to find all permutations of String? (solution)
  • How to find duplicate characters in a String? (solution)
  • How to reverse String in Java using Iteration and Recursion? (solution)
  • How to count the occurrence of a given character in String? (solution)
  • How to reverse words in a sentence without using a library method? (solution)
  • How to reverse a String in place in Java? (solution)
  • 10 Algorithms Courses to Crack Programming Job Interviews (courses)
  • How to return the highest occurred character in a String? (solution)

Thanks for reading this coding interview question so far. If you like this String coding interview question then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you want to learn Data Structure and Algorithms in-depth or just want to revise key data structure concepts before an interview and looking for free resources then you should also check this list of Free Data Structure and Algorithms Courses for Programmers. It contains the best free online courses from Udemy, Coursera, and Educative to learn Data structure and Algorithms. 

And, now one question for you, what is your favorite coding problem? Factorial, Pattern based problem, Palindrome or Armstrong number? or anything else, do let me know in comments. 

No comments:

Post a Comment

Feel free to comment, ask questions if you have any doubt.