Remove Vowels

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.

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

Deleting characters one at a time from the middle of a string shifts everything after each gap. Build the answer instead: walk the string once and copy every letter that is not a vowel. Get the capital vowels right, and assemble the result in a builder.

Delete each vowel with its own pass

Intuition

Most languages delete every copy of one character in a single call: replace it with nothing. Do that once for each of a e i o u A E I O U. The consonants are never touched, so they keep their order and case. For Interview, the passes for e, i and I give Intrviw, Intrvw and ntrvw; the other seven find nothing.

Each pass reads the whole string, about 10n steps in total. That is still O(n), but for 3 × 10^4 letters it is 3 × 10^5 steps where one 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

Collect what stays instead of deleting what goes. Walk s once and append each character that is not one of the ten vowel letters. You append in reading order and never change a character, so the consonants keep their order and case.

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). Append to a builder or a list and turn it into a string once at the end. 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

Forgetting capital vowels. Testing only aeiou turns Interview into Intrvw instead of ntrvw.
Lower-casing the whole string to shorten the test. QUEUEING then comes back as qng instead of QNG. Lower-case only the copy you test.
Deleting while walking forward by index. Removing s[i] shifts the next letter into position i, and i++ skips it, so aab comes back as ab.
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.

Frequently asked questions3

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.

def removeVowels(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "Interview"

Expected Output

"ntrvw"