The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

You are given a string. You are asked to: A) remove all occurrences of a particular character in the string, of the same case, and B) remove all occurrences of a particular character in the string, independent of case.

You are asked to employ O(N) time and O(N) space for each problem.

A) Remove all occurrences of a particular character in the string, of the same case.

To remove all of the lowercase 'o', for an input of

    "Broad Network Corporation"

the output would be

    "Brad Netwrk Crpratin"

Just iterate over the whole string in O(N) time removing any occurrence of 'o'. There is no shorter (more efficient) way of doing this. The program is (read through the code and comments):

#include 

void removeCharCase(char str[], char ch, int N) {
    int charCounter = 0;    //number of particular character
    int i;
    for (i = 0; i < N; i++) {
        if (str[i] == ch) {    //no need to test case
            charCounter += 1;
            continue;   
        } 
        else {
            str[i - charCounter] = str[i];
        }
    }
    
    //end string just after the new shortened length
    str[N-charCounter] = '\0';
}

int main(int argc, char **argv) {
    int N = 0;    //length (size) of string to be determined in function below
    char stri[] = "Broad Network Corporation";    //given string
    
    char *ptr = stri;
    while (*ptr != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr++; 
        N += 1;
    }

    removeCharCase(stri, 'o', N);
    
    // Print toggled characters
    int i=0;
    while (stri[i] != '\0') {
        printf("%c ", stri[i]);
        i++;
    }
    printf("\n");

    return 0;
}

The output is:

    "BB r a d   N e t w r k   C r p r a t i n"

as expected. The time complexity is actually O(2N), with O(N) for finding the length of the input string array and O(N) for iterating over the string array in the called function. However, the coefficient (multiplier of 2 or 3 or 1/2, etc.) is normally omitted. The space complexity is O(N), since the input string array and the string array in the called function are the same array.

B) Remove all occurrences of a particular character in a string, independent of case.

To remove all of the upper and lower case 'W', for an input of

    "We are the world"

the output would be

    "e are the orld"

There is need to compare the particular character in one case, either upper or lower; without changing the case. The comparison has to be done in one case, because both cases of the same character have different number codes. Lower is chosen for the program below.

The ctype.h library which has the tolower() predefined function, is imported. The tolower() function operates in approximately O(1) time, which is ignored when quoting the time complexity. Any temporary space used by this predefined function is also ignored, when quoting the space complexity. The following program illustrates all these (read through the code and comments):

#include 
#include 

void removeChar(char str[], char ch, int N) {
    int charCounter = 0;    //number of particular character
    int i;
    for (i = 0; i < N; i++) {
        char chSL = tolower(str[i]);    //each of the characters in the given string goes lower, temporarily
        char chGL = tolower(ch);    //the particular character goes lower
        if (chSL == chGL) {    //test case
            charCounter += 1;
            continue;   
        } 
        else {
            str[i - charCounter] = str[i];
        }
    }
    
    //end string just after the new shortened length
    str[N-charCounter] = '\0';
}

int main(int argc, char **argv) {
    int N = 0;    //length (size) of string to be determined in function below
    char stri[] = "We are the world";    //given string
    
    char *ptr = stri;
    while (*ptr != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr++; 
        N += 1;
    }

    removeChar(stri, 'W', N);
    
    // Print toggled characters
    int i=0;
    while (stri[i] != '\0') {
        printf("%c ", stri[i]);
        i++;
    }
    printf("\n");

    return 0;
}

The output is:

    "e   a r e   t h e   o r l d"

as expected. The time complexity is officially O(N) and the space complexity is officially O(N).

Thanks for reading.