Remove Leading/duplicate/trailing spaces
" My dog is great " --> "My dog is great"
Solution: Fast slow pointers
Two cases:
i == " "
first space of string: dont copy
duplicate space: dont copy
first space after char: copy
i != " " copy
public String removeSpace(String input) {
if (input.isEmpty()) return input;
char[] array = input.toCharArray();
int slow = 0;
for (int i = 0; i < array.length; i++){ //fast pointer
char current = array[i];
if (char == ' ' && (i == 0 || array[i - 1] == ' ')){
continue;
}
array[slow++] = char;
}
//process possible last space
if (slow > 0 && array[slow] == ' ') return new String(array, 0, slow - 1);
return new String(array, 0, slow);
Time comp: 1.5 traversals max = O(N)
Space comp: new char[] = O(N)
Last updated
Was this helpful?