LeetCode 1119 - Remove Vowels from a String

LeetCode Problem 1119

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to remove vowels from a given string s. Specifically, the vowels are defined as the lowercase characters 'a', 'e', 'i', 'o', and 'u'. The input string consists only of lowercase English letters, and its length ranges from 1 to 1000. The expected output is a string that contains all the original characters from s except for the vowels, preserving the original order of the consonants.

The constraints are fairly small: a maximum of 1000 characters means that even simple iterative solutions will run efficiently. Edge cases include strings that are all vowels, strings with no vowels, and strings with a single character. These edge cases could easily trip up a naive implementation if, for example, it assumes there is at least one consonant.

Approaches

A brute-force approach would iterate through each character in the string and, for every character, check if it is a vowel. If it is not a vowel, we append it to a new string. This approach works correctly, but it involves repeated membership tests that can be optimized.

The optimal approach uses a set to store the vowels. By using a set, membership checking becomes O(1) per character. We then iterate through the string once, building a new string (or list of characters) that excludes vowels. This approach is straightforward, efficient, and leverages a simple Python or Go idiom for string building.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n)	Check each character against a list of vowels (m = number of vowels, 5)
Optimal	O(n)	O(n)	Use a set for O(1) membership checks and build result incrementally

Algorithm Walkthrough

1. Create a set containing all vowels: {'a', 'e', 'i', 'o', 'u'}. This allows O(1) membership checking for each character.
2. Initialize an empty list to store the resulting characters.
3. Iterate over each character in the input string.
4. For each character, check if it is not in the vowels set.
5. If it is not a vowel, append it to the result list.
6. After processing all characters, join the list into a single string.
7. Return the resulting string.

Why it works: The algorithm guarantees that every character from the original string is examined exactly once, and only non-vowel characters are preserved. Using a set ensures efficient vowel checking, and constructing a new string preserves the order of the consonants.

Python Solution

class Solution:
    def removeVowels(self, s: str) -> str:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        result = []
        for char in s:
            if char not in vowels:
                result.append(char)
        return ''.join(result)

The Python implementation follows the algorithm directly. We first define a set of vowels, then initialize an empty list result to accumulate consonants. For each character in the string, we check if it is not a vowel, appending it to result if it passes the test. Finally, ''.join(result) concatenates the list into a single string to return.

Go Solution

func removeVowels(s string) string {
    vowels := map[rune]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
    }
    result := []rune{}
    for _, char := range s {
        if !vowels[char] {
            result = append(result, char)
        }
    }
    return string(result)
}

In Go, we use a map[rune]bool to store the vowels for O(1) membership checking. The string is iterated using a for _, char := range s loop to handle each character as a rune. Non-vowel characters are appended to a slice of runes, which is then converted back to a string using string(result).

Worked Examples

Example 1: "leetcodeisacommunityforcoders"

Iteration	char	in vowels?	result list
1	'l'	no	['l']
2	'e'	yes	['l']
3	'e'	yes	['l']
4	't'	no	['l', 't']
5	'c'	no	['l', 't', 'c']
6	'o'	yes	['l', 't', 'c']
...	...	...	...
final	-	-	['l', 't', 'c', 'd', 's', 'c', 'm', 'm', 'n', 't', 'y', 'f', 'r', 'c', 'd', 'r', 's']

Output: "ltcdscmmntyfrcdrs"

Example 2: "aeiou"

All characters are vowels, so the result list remains empty. Output: "".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through each character once and perform O(1) membership checks in a set
Space	O(n)	We store up to n characters in the result list

Because n is at most 1000, both time and space usage are trivial for modern systems.

Test Cases

# Provided examples
assert Solution().removeVowels("leetcodeisacommunityforcoders") == "ltcdscmmntyfrcdrs"  # mixed string
assert Solution().removeVowels("aeiou") == ""  # all vowels

# Boundary cases
assert Solution().removeVowels("b") == "b"  # single consonant
assert Solution().removeVowels("a") == ""  # single vowel

# No vowels
assert Solution().removeVowels("bcdfghjklmnpqrstvwxyz") == "bcdfghjklmnpqrstvwxyz"  # all consonants

# Mixed vowels and consonants
assert Solution().removeVowels("programmingisfun") == "prgrmmngsfn"  # mixed string

Test	Why
"leetcodeisacommunityforcoders"	general mixed input
"aeiou"	all vowels removed
"b"	single consonant edge case
"a"	single vowel edge case
"bcdfghjklmnpqrstvwxyz"	no vowels, ensure consonants are preserved
"programmingisfun"	standard mixed string

Edge Cases

One edge case is a string consisting entirely of vowels, such as "aeiou". This tests whether the implementation correctly returns an empty string rather than accidentally inserting placeholder characters. Our solution handles this naturally by only appending non-vowels to the result list.

A second edge case is a string consisting entirely of consonants. This tests that the algorithm does not remove valid characters. Using a set membership check ensures that all consonants are preserved because they are never in the vowel set.

A third edge case is a single-character string, either a vowel or consonant. This is important to ensure that the algorithm handles minimal input sizes without errors, and our implementation correctly returns either the same character or an empty string depending on whether the character is a vowel.