Remove Blank spaces in a string in O(n).

Question

How to remove blank spaces in a string with a complexity of O(n). My approach is using two indexes. One will traverse till length on string. Other will be incremented only when a non-blank character is encountered. But i am not sure of this approach.

TIA, Praveen

Answer 1

Your approach sounds fine, and meets the requirement.

Answer 2

This approach is fine. The O(n) requirement simply means that the running time is proportional to the number of items which in this case means the number of characters in the string (assuming you mean time complexity which is a fairly safe bet here).

The pseudocode:

def removeSpaces (str):
    src = pointer to str
    dst = src
    while not end-of-string marker at src:
        if character at src is not space:
            set character at dst to be character at src
            increment dst
        increment src
    place end-of-string marker at dst

is basically what you're trying to do.

Because it has a single loop dependent only on the number of characters, it is indeed O(n) time complexity.

---

The following C program shows this in action:

#include <stdio.h>

// Removes all spaces from a (non-const) string.

static void removeSpaces (char *str) {
    // Set up two pointers.

    char *src = str;
    char *dst = src;

    // Process all characters to end of string.

    while (*src != '\0') {
        // If it's not a space, transfer and increment destination.

        if (*src != ' ')
            *dst++ = *src;

        // Increment source no matter what.

        src++;
    }

    // Terminate the new string.

    *dst = '\0';
}

 

// Test program.

int main (void)
{
    char str[] = "This is a long    string with    lots of spaces...   ";
    printf ("Old string is [%s]\n", str);
    removeSpaces (str);
    printf ("New string is [%s]\n", str);
    return 0;
}

Running this gives you:

Old string is [This is a long    string with    lots of spaces...   ]
New string is [Thisisalongstringwithlotsofspaces...]

Note that, if there are no spaces in the string, it simply copies every character over itself. You might think that you could optimise it by checking if src == dst and not copying but you'll probably find the check is as expensive as the copy. And, unless you're frequently copying multi-megabyte strings, performance won't be an issue here.

Also keep in mind this will be undefined behaviour with const strings but that would be the case in any in-place modification.