Sunday, July 2, 2017

Remove all adjacent or consecutive duplicate characters

Remove all adjacent or consecutive duplicate characters


Input:  azxxzy
Output: ay
First "azxxzy" is reduced to "azzy". The string "azzy" contains duplicates, 
so it is further reduced to "ay".

Input: geeksforgeeg
Output: gksfor
First "geeksforgeeg" is reduced to "gksforgg". The string "gksforgg" contains 
duplicates, so it is further reduced to "gksfor".

Input: caaabbbaacdddd
Output: Empty String

Input: acaaabbbacdddd
Output: acac

Iterate through the characters and keep track of duplicates with start and end index, once you get a non matching character then delete the start to end characters and step back one more step and start again.

private static String removeAllAdjacentDuplicates(String s) {
StringBuilder sb = new StringBuilder(s);
int startIndex = -1;
int endIndex = -1;
char previousChar = '\0';
for (int i = 0; i < sb.length(); i++) {
if (previousChar == sb.charAt(i))
endIndex = i;
else {
if (endIndex > startIndex) {
sb.delete(startIndex, endIndex + 1);
i = --startIndex;
i = i < 0 ? 0 : i;
endIndex = -1;
}
startIndex = i;
previousChar = sb.charAt(i);
}
}
if (endIndex > startIndex)
sb.delete(startIndex, endIndex + 1);

return sb.toString();
}

Note: Deleting is a costly operation for that all the elements will be left shifted with their position.

No comments:

Post a Comment