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

    fn remove_char_case(stri: &mut String, ch: char) {    //use reference to avoid unnecessary recopying of string
        let mut characters: Vec<char> = stri.chars().collect();
        let n = characters.len();    //length of string
    
        let mut char_counter = 0;    //number of particular character
        for i in 0..n {
            if characters[i] == ch {    //no need to test case
                char_counter += 1;
                continue;   
            } 
            else {
                characters[i - char_counter] = characters[i];
            }
        }
        
        // Cut off the leftover characters towards the right end
        characters.truncate(n - char_counter);
        
        //Output
        for c in characters {
            print!("{}", c);
        }
        println!(); // Print a newline at the end
    }

fn main() {
    let mut stri = String::from("Broad Network Corporation");    //given string
    remove_char_case(&mut stri, 'o');
}

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

    fn remove_char(stri: &mut String, ch: char) {    //use reference to avoid unnecessary recopying of string
        let mut characters: Vec<char> = stri.chars().collect();
        let n = characters.len();    //length of string
    
        let mut char_counter = 0;    //number of particular character
        for i in 0..n {
            let ch_sl = characters[i].to_ascii_lowercase();    //each of the characters in the given string goes lower, temporarily
            let ch_gl = ch.to_ascii_lowercase();    //the particular character goes lower
            if ch_sl == ch_gl {    //test case
                char_counter += 1;
                continue;   
            } 
            else {
                characters[i - char_counter] = characters[i];
            }
        }
    
        // Cut off the leftover characters towards the right end
        characters.truncate(n - char_counter);
        
        //Output
        for c in characters {
            print!("{}", c);
        }
        println!();    // Print a newline at the end
    }

fn main() {
    let mut stri = String::from("We are the world");    //given string
    remove_char(&mut stri, 'W');
}

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.