# Remove duplicate characters

Tags: ,

Given a string, remove consecutive duplicate characters from the string. For example:

```Input:
S = "aabccacc"
Output:
"ba"

Input:
S = "accacc"
Output:
""
```

Solution for this problem is in the idea that we need two pointers, one to read a character and another to write a character.
In this case, let’s say we take two pointers, i and j, where i points to the index where next character will be written, whereas j will is the position of current character.

As String in most languages is an immutable object and we are planning to modify it, it is better idea to convert string to a character array. For each character at index j, we will copy it at index i. Check if the chars[i-1] and chars[i] are equal? If yes, we found consecutive duplicate characters.
If found duplicate characters, we will move i to i-2 to remove both instances of the character. If not, nothing changes.

## Removed consecutive duplicates from string implementation

```package AlgorithmsAndMe;

public class RemovedDuplicates {

public String removeDuplicates(String s){

char [] res =  s.toCharArray();
int i = 0;
int [] count = new int[res.length];
for(int j=0; j<res.length; j++, i++){
res[i] = res[j];

if(i > 0 && res[i] == res[i-1]){
i -=2;
}
}

return String.valueOf(res).substring(0, i);

}
}
```

Sometimes the same question is asked with k as parameters: given a string, remove all consecutive K duplicate characters.
For example:

```Input:
S =  deeedbbcccbdaa, K = 3.
Output:
"aa"
```

The idea is the same, keep two pointers i and j, one for writing and another for reading. We will copy the character onto the index i. If the new character is the same as the previous character, we increment the count. If not, we reset the count. If count is equal to k, we remove all the instance of the character by moving i by k to the left.

```package AlgorithmsAndMe;

public class RemovedDuplicates {

public String removeDuplicates(String s, int k){

char [] res =  s.toCharArray();
int i = 0;
int [] count = new int[res.length];
for(int j=0; j<res.length; j++, i++){
res[i] = res[j];

count[i] = i>0 && res[i-1] == res[j] ? count[i-1] + 1 : 1;

if(count[i] == k){
i -=k;
}
}

return String.valueOf(res).substring(0, i);

}
}
```

The time complexity of both the implementations is O(n).