Remove Element String

Problem Statement

Given a string in memory of size $n$ , remove all instances of that value in-place and return the new length. Assume the string is null-terminated.


// Assume the string is Null Terminated 
int remove_element(char* arr, char to_remove){
	// Your Code Here
}

Note:

This problem requires a low level implementation. Think of an string not as something that you would see in python, where relevant information such as size/etc is stored, but as something you would see in C, where information about lengths of strings are not necessarily given when they are null-terminated.

Test Cases

Test Case 1

Calling the function on "aeiouabc\0" and 'a' should return 6 and the string should now be "eioubc\0"

Test Case 2

Calling the function on "bcdef\0" and 'p' should return 5 and the string should now be "bcdef\0"

Follow Up Questions To Think About

Suppose the array was instead a linked list. How would this implementation change, and what would be the consequences.

Click Below to see the Solution

Algorithm

The idea here is to iterate through the array and copy the array back onto itself as we go. We will only increment the index when we see an element that is not the character we have to remove.

Code

int remove_element(char* arr, char to_remove){

	int i = 0;
	int j = 0;
	while(arr[i] != '\0'){
		if(arr[i] != to_remove){
			arr[j] = arr[i];
			j++;
		}
		i++;
	}
	arr[j] = '\0'
	return j;
}

Runtime Analysis

We iterate through the array exactly once, so the computational complexity is $O(n)$ . In terms of the number of writes, we write to the array once for each element in the final array, so this is $O(m)$ where $m$ is the length of the final array.