Thursday, October 10, 2013

Removing a given character from the string

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.