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