Given a string and a character, Write a function to remove all instances of the character and return the modified string.
One easy method is to iterate through each character of the string, Once a restricted character is seen, we move all the characters appearing after it by one position. This approach involves a lot of shift operations and in worst case it takes O(n2) time.
We can be more efficient if we follow the approach given below.
Take two indices; one running index (i) and one result index (r). All the valid characters are copied to beginning of the string and both indices are incremented. If a prohibited character is seen, we skip that character and just increment i. At the end, we re-size the string so that the characters beyond the index ‘r’ are removed.
Let us understand this with a simple example.
Let the input string be ‘PROGRAM’ and we want to remove the letter ‘R’. The following table illustrates the behavior of the algorithm by iteration.
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
|
P
|
R
|
O
|
G
|
R
|
A
|
M
|
|
P
|
R
|
O
|
G
|
R
|
A
|
M
|
|
P
|
R
|
O
|
G
|
R
|
A
|
M
|
|
P
|
O
|
O
|
G
|
R
|
A
|
M
|
|
P
|
O
|
G
|
G
|
R
|
A
|
M
|
|
P
|
O
|
G
|
G
|
R
|
A
|
M
|
|
P
|
O
|
G
|
A
|
R
|
A
|
M
|
|
P
|
O
|
G
|
A
|
M
|
A
|
M
|
The shaded part indicates the result string that is formed in-place without using the extra space.