Java Program to Remove All Adjacent Duplicates from String

«
»

This is the Java Program to Delete Adjacent Pairs of Repeated Characters.

Problem Description

Given a string, find and remove all the adjacent pairs of repeated characters.

Example:

String x = “ABBCCCD”
Output = “ACD”

Problem Solution

Create a stack and push the first character of the string on it. Now, iterate through the string, and check whether the current character of the string is at the top of the stack. If it is, then pop it off the stack. Form a string from the characters left in the string and reverse it.

Program/Source Code

Here is the source code of the Java Program to Delete Adjacent Pairs of Repeated Characters. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
  1.  
  2. // Java Program to Delete Adjacent Pairs of Repeated Characters.
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.util.Stack;
  8.  
  9. public class AdjacentCharacters {
  10.     // Function to remove adjacent characters
  11.     static String removeAdjacentRepeatedCharacters(String str){
  12.         Stack<Character> stack = new Stack<>();
  13.         int i;
  14.         stack.push(str.charAt(0));
  15.         for(i=1; i<str.length(); i++){
  16.             if(stack.peek() == str.charAt(i)){
  17.                 stack.pop();
  18.                 continue;
  19.             }
  20.             stack.push(str.charAt(i));
  21.         }
  22.         StringBuffer obj = new StringBuffer();
  23.         while(!stack.isEmpty()){
  24.             obj.append(stack.pop());
  25.         }
  26.         return obj.reverse().toString();
  27.     }
  28.     // Function to read the input and display the output
  29.     public static void main(String[] args) {
  30.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  31.         String str;
  32.         System.out.println("Enter the string");
  33.         try {
  34.             str = br.readLine();
  35.         } catch (IOException e) {
  36.             System.out.println("An I/O error occurred");
  37.             return;
  38.         }
  39.         String newString =removeAdjacentRepeatedCharacters(str);
  40.         System.out.println("The new string is \"" + newString + "\"");
  41.     }
  42. }
Program Explanation

1. In function removeAdjacentRepeatedCharacters(), a stack is created and the first character of the string is pushed onto the stack.
2. The loop for(i=1; i<str.length(); i++) iterates through the rest of the string.
3. The condition if(stack.peek() == str.charAt(i)) checks if the current character of the string is equal to the character at the top of the stack.
4. If it is, a character is popped from the stack otherwise the current character of the string is pushed onto the stack.
5. The loop while(!stack.isEmpty()) add all the characters of the stack to a StringBuffer object and the reverse of the object is returned.

Time Complexity: O(n) where n is the length of the string.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the string
ABBCCCD
The new string is "ACD"
 
Case 2 (Simple Test Case - another example):
 
Enter the string
XYZ
The new string is "XYZ"

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.