Remove Vowels

Q: How do you remove vowels from a string?

Walk the string once and copy each letter that is not a , e , i , o or u (in either case) into a builder or a list. Join it into a string at the end. The order and the case of the kept letters stay as they were.

Q: What is the time complexity of removing vowels?

One pass is O(n) time, because each character gets one constant-time vowel test. The output takes O(n) space in the worst case, when s has no vowels at all. Calling replace once per vowel is also O(n) , but it reads the string ten times.

Q: Can you remove vowels with a regular expression?

Yes. Replacing the pattern [aeiouAEIOU] with an empty string does it in one call in most languages. It runs in O(n) , the same as the loop, but interviewers usually ask you to write the loop so they can see the vowel test and how you build the result.

BeginnerArrays and strings

+10

You get a string s made of English letters. Return the string you get by deleting every vowel from it. The vowels are a, e, i, o and u, in lower or upper case; y is not a vowel here. The letters that stay keep their order and their case.

Function

removeVowels(s: string) → string

sstring: the string of English letters to clean
Returnsstring: s with every vowel removed and the other letters in their original order

Constraints

1 ≤ s.length ≤ 3 × 10⁴
s contains only English letters (a to z, A to Z).
s contains at least one letter that is not a vowel, so the answer is never empty.

Examples

Input: s = "Interview"
Output: "ntrvw"
Explanation: Deleting I, e, i and e from Interview leaves n, t, r, v, w in that order. The capital I is a vowel too, so it goes.

Input: s = "rhythm"
Output: "rhythm"
Explanation: rhythm has no a, e, i, o or u, so nothing is deleted. Its y is not on the vowel list and stays.

Input: s = "EuropeanUnion"
Output: "rpnnn"
Explanation: Eight of the thirteen letters of EuropeanUnion are vowels, the capital E and U included. The five consonants that remain, r, p, n, n, n, keep their order and read rpnnn.

+17 hidden tests on Submit

Follow-up

What if the text could hold any Unicode letter, such as É or ö? Which of them are vowels, and how does your test change?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Removing characters from the middle of a string is costly if you do it one deletion at a time, because everything after the gap shifts over. The better plan is to build the answer instead: walk the string once and copy every letter that is not a vowel. The details to get right are the capital vowels and how the result is assembled.

Delete each vowel with its own pass

Intuition

Most languages can delete every copy of one character from a string in a single call: replace it with nothing. Do that ten times, once for each of a e i o u A E I O U, and no vowel is left. The consonants are never touched, so they keep their order and case.

For Interview, the pass for e gives Intrviw, the pass for i gives Intrvw, and the pass for I gives ntrvw. The other seven passes find nothing to remove.

Each pass reads the whole current string, so the work is about 10n character steps. That is still O(n), because ten is a constant, but for 3 × 10^4 letters it means 3 × 10^5 steps where a single walk needs 3 × 10^4.

Algorithm

Take the ten vowel letters aeiouAEIOU one at a time.
For each one, replace every copy of it in s with nothing.
After the ten passes, return what is left of s.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

One pass that keeps the consonants

Intuition

Turn the job around: instead of deleting vowels, collect everything else. Walk s once, and for each character ask whether it is one of the ten vowel letters. If it is not, append it to the result. Since you append in reading order and never change a character, the order and the case of the consonants come out exactly as they went in.

For EuropeanUnion, the walk skips E, u, o, e, a, U, i and o, and appends r, p, n, n, n: the result is rpnnn.

Each character costs one constant-time test (a set lookup, a switch, or a search in a ten-letter string), so the time is O(n). Collect the letters in a builder or a list and turn it into a string once at the end; growing an immutable string with += would copy it on every step. The output itself is the O(n) space.

Algorithm

Start an empty builder for the result.
Walk s one character at a time.
If the character is not one of aeiouAEIOU, append it to the builder.
Return the builder as a string.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

Pitfalls and edge cases

Most wrong answers come from the vowel test or from how the result string grows.

Forgetting capital vowels. Testing only aeiou turns Interview into Intrvw instead of ntrvw. Check all ten letters, or lower-case the character before the test, and keep the original character in the output.
Changing the case of the kept letters. If you lower-case the whole string to make the test shorter, QUEUEING comes back as qng instead of QNG. Lower-case only the copy you test, and append the original character.
Deleting while walking forward by index. Removing s[i] shifts the next letter into position i, and then i++ skips it, so aab comes back as ab. Build a new string, or walk with separate read and write positions.
Growing an immutable string with += in a loop. In Java or C# each step copies the whole string, about 4.5 × 10^8 character copies for 3 × 10^4 letters. Use a builder or a list and join it once.

Frequently asked questions4

How do you remove vowels from a string?

Walk the string once and copy each letter that is not a, e, i, o or u (in either case) into a builder or a list. Join it into a string at the end. The order and the case of the kept letters stay as they were.

What is the time complexity of removing vowels?

One pass is O(n) time, because each character gets one constant-time vowel test. The output takes O(n) space in the worst case, when s has no vowels at all. Calling replace once per vowel is also O(n), but it reads the string ten times.

Can you remove vowels with a regular expression?

Yes. Replacing the pattern [aeiouAEIOU] with an empty string does it in one call in most languages. It runs in O(n), the same as the loop, but interviewers usually ask you to write the loop so they can see the vowel test and how you build the result.

Why not delete the vowels from the string in place?

Deleting one character from the middle shifts every later character left, so many deletions can cost O(n²). You can do it in place in O(n) with two indexes, one that reads every character and one that writes the next kept letter, but in most languages strings cannot be changed, so building a new string is the natural route.

Python

def removeVowels(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "Interview"

Expected

"ntrvw"