WAP to Remove Remove vowels from a string in place.

This is asked in many preliminary tech interviews.

Question:

Write a program to remove all vowels from a string in place.

The key to solving this is that since we are removing characters from the string, the resultant string length will be less than or equal to the original string's length. So, the idea here would be to accumulate all the vowels and push them towards the end of the string and at the end, if we keep a running count of the number of vowels in the string and we already know the length of the original string, we can place our C string terminating null char at the appropriate position to give us a new string, sans the vowels. The algorithm in plain words is as follows:

We run across the word from left to right. The first time we encounter a vowel, we store that position (the index if you look at the string as a char array) in the string in a variable.

Each time we encounter a consonant we swap its position with the position of the vowel and just increment the index that points to the vowel. If another vowel is encountered, we just increment a count that stores the vowels encountered thus far.

This keeps all the vowels contiguous in the string and as each swap with a consonant happens, this contiguous block of vowels gets pushed further down the string until we reach the end of string. We can then just put a null char at (n - vowel_count) where n is the length of the original string.

For the example word PEEPERS:

1. vowel_count=0, vowel_start_index=-1
2. P is encountered first, do nothing because we haven't come across a vowel yet.
3. E is encountered next, so vowel_count=1 and vowel_start_index=1 (assuming 0 based array indices. So the first E is at position number 1 in the string PEEPERS
4. E is encountered again, so vowel_count=2
5. P is encountered next, its a consonant so swap position of P with position held in vowel_start_index. Then increment vowel_start_index. So the string looks like PPEEERS and vowel_start_index=2
6. E is encountered next (this is the third E in PEEPERS). vowel_count becomes 3.
7. R is encountered. Its a consonant so swap it with character held at vowel_start_index (which is 2). So the string becomes PPREEES and increment vowel_start_index to 3
8. Finally we come across S. Do the same as above and whola!! You have the string PPRSEEE with vowel_count = 3.
9. Now just place a null at (n - vowel_count) = 7-3 = 4 and you have the string PPRS which is the desired output.

The code is as follows. It uses C++ string but can easily be emulated for C style strings.
We scan through the string only once and no extra storage space is used. So time complexity is O(n) and space complexity is O(1).

#include

bool isVowel(char a)
{
if(a == 'a' || a == 'A' ||
a == 'e' || a == 'E' ||
a == 'i' || a == 'I' ||
a == 'o' || a == 'O' ||
a == 'u' || a == 'U')
return true;
else
return false;
}

void removeLetters(std::string& s)
{
int len = s.length();
int vcount = 0;
int vstart = -1;

for(int i=0; i {
if(isVowel(s[i]))
{
if(vstart == -1)
vstart = i;
vcount++;
}

if(!isVowel(s[i]) && vstart != -1)
{
/* Encountered letter is a consonant. So do swap.
The below method for swap does not need a tmp variable */
s[i] = s[i] + s[vstart];
s[vstart] = s[i] - s[vstart];
s[i] = s[i] - s[vstart];
vstart++;
}
}
s = s.substr(0, len-vcount);
}

int main(int argc, char** argv)
{
std::string s = "the rain in spain is mainly from the plains.";
removeLetters(s);
std::cout << s << std::endl;
return 0;
}