Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in JavaScript

Remove all Adjacent Duplicates from a String

Explore how to use recursion to remove all adjacent duplicate characters in a string while preserving case sensitivity. Understand the base and recursive cases that allow the function to process the string by comparing characters and reducing string length with each call. This lesson equips you with the skills to handle string manipulation challenges in coding interviews effectively.

We'll cover the following...

What does “Removing Adjacent Duplicates from a String” Mean?

This means that we’ll remove all extra instances of a character when multiple instances are found together. In other words, only one instance should remain after this process.

Lower and upper case letters are considered different characters. Example: string Hhelo doesn’t contain any duplicates.

Repeated occurrences of the same letter within a string are allowed as long as they are not next to each other. Example: string hele has no adjacent duplicates.

widget

Implementation

Javascript (babel-node)
function removeDuplicates(string) {
  // Base case
  if (string.length <= 1) {
      return string;
  }
  // Recursive case1
  else if (string[0] == string[1]) {
      return removeDuplicates(string.substr(1));
  }
  // Recursive case2
  return string[0] + removeDuplicates(string.substr(1));
}
// Driver Code
console.log(removeDuplicates('Hellloo'));

Explanation

To remove duplicates, we reduce the length of the string with each recursive call. If the current character is similar to the following character, we discard its first occurrence and repeat the process recursively on the rest of the string. However, if the current character is not similar to the following character, we keep it. We append it when the child function returns.

The code snippet above checks for 33 cases:

  1. (Line number 3 to 5) If the length of the string is less than or equal to 11.
    • There can be no duplicates in a string that contains only 11 character or no characters so we return the string variable in this case.

Condition 11 is the base case since there is no string manipulation occurring in this case.

  1. (Line number 8 to 10) If the first and second elements of the string are same.

    • In this case, we discard the first occurrence and recursively call the same function with the first letter removed.

  2. (Line number 13) If none of these 22 conditions are satisfied, we save the first element for later use and call the same function again with the first element removed. The saved element will be later appended to the beginning of the string when the recursive call returns.

Let’s take a look at the sequence of function calls:

In the next lesson, we’ll learn how to merge strings lexicographically.