Remove Leading/duplicate/trailing spaces

" My dog is great " --> "My dog is great"

Solution: Fast slow pointers

Two cases:

i == " "

  1. first space of string: dont copy

  2. duplicate space: dont copy

  3. 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?