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):

def RemoveCharCase(str, ch):
    N = len(str);    #length of string
    
    charCounter = 0;    #number of particular character
    
    strlist = list(str)    # for mutation since string content is constant

    for i in range(N):
        if (strlist[i] == ch):    #no need to test case
            charCounter += 1;
            continue;   
        else:
            strlist[i - charCounter] = strlist[i]

    # Cut off leftover characters at the end
    del strlist[N - charCounter:]
    
    # Join list back into a string
    str = "".join(strlist)
    return str

#main area
stri = "Broad Network Corporation";    #given string
sr = RemoveCharCase(stri, 'o');
print(sr); 

The output is:

    "B 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):

def RemoveChar(str, ch):
    N = len(str);    #length of string
    
    charCounter = 0;    #number of particular character
    
    strlist = list(str)    # for mutation since string content is constant

    for i in range(N):
        chSL = strlist[i].lower();    #each of the characters in the given string goes lower, temporarily
        chGL = ch.lower();    #the particular character goes lower
        if chSL == chGL:    #test case
            charCounter += 1;
            continue;   
        else:
            strlist[i - charCounter] = strlist[i];
            
    # Cut off leftover characters at the end
    del strlist[N - charCounter:]
    
    # Join list back into a string
    str = "".join(strlist)
    return str

#main area
stri = "We are the world";    #given string
sr = RemoveChar(stri, 'W');
print(sr); 

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.