1119. Remove Vowels from a String

EasyString
Leetcode Link

Problem Description

In this problem, we are given a string s that consists of lowercase letters. Our task is to remove all the vowels from this string. The vowels that we need to remove are 'a', 'e', 'i', 'o', and 'u'. After removing all these vowels from the string s, we should return the resulting string.

The main challenge is to process the string and efficiently eliminate the characters that are considered vowels.

Intuition

The intuitive approach to solving this problem is to create a new string by iterating over each character in the original string and including only the characters that are not vowels. We can accomplish this by checking every character in the string s and appending it to the new string if it is not 'a', 'e', 'i', 'o', or 'u'.

To make our code more concise and Pythonic, we use a generator expression inside the join method. A generator expression is an elegant way to transform each item from a sequence according to a given condition or rule. In our solution:

  1. We iterate over each character c in the string s.
  2. We check if c is not in the string "aeiou" which contains all the vowels we want to exclude.
  3. If c is not a vowel, it is included in the generator expression.
  4. The "".join() function is used to concatenate all the characters accepted by our condition into a new string without vowels.

This approach is straightforward, avoids the use of additional data structures, and leverages the power of Python's string handling capabilities.

Solution Approach

The implementation for removing vowels from a string in the given solution can be outlined as follows:

  1. Data Structure: We use a simple string data structure. Strings in Python are immutable, so we're actually creating a new string as we iterate through the original one.

  2. Algorithm: The core of the algorithm is a traversal of the input string s. This is the classic iteration pattern.

  3. Patterns Used: We make use of a generator expression, which is an efficient way to handle sequences in Python. It provides a concise way to handle elements one by one, applying a filter or function to each one.

The steps of the algorithm are as follows:

  • We begin by defining a class Solution, which will contain our method removeVowels.

  • Inside removeVowels, we perform a generator expression "".join(c for c in s if c not in "aeiou").

    • c for c in s: This part creates a generator that goes through each character c in the string s.

    • if c not in "aeiou": This condition serves as a filter. It checks whether each character c is not one of the vowels 'a', 'e', 'i', 'o', or 'u'.

    • "".join(...): This function takes all characters that pass the filter (i.e., all non-vowel characters) and joins them together into a new string. The "" indicates that we are not using any delimiter between characters, so they are simply concatenated together.

The efficiency of this approach lies in the fact that we avoid constructing intermediary lists or arrays; we are directly constructing the new string without vowels in a single pass through the input string.

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the string s = "leetcode".

  1. We start by creating an instance of the Solution class.
  2. We invoke the removeVowels method and pass our example string s to it.
  3. The removeVowels method begins executing a generator expression within a join function.
  4. The generator iterates over each character in s. Here's how it processes our example:
    • 'l': Since 'l' is not in "aeiou", it passes the filter. The generator yields 'l'.
    • 'e': 'e' is a vowel; it does not pass the filter and is not yielded by the generator.
    • 'e': 'e' is a vowel; it does not pass the filter and is not yielded by the generator.
    • 't': Since 't' is not in "aeiou", it passes the filter. The generator yields 't'.
    • 'c': Since 'c' is not in "aeiou", it passes the filter. The generator yields 'c'.
    • 'o': 'o' is a vowel; it does not pass the filter and is not yielded by the generator.
    • 'd': Since 'd' is not in "aeiou", it passes the filter. The generator yields 'd'.
    • 'e': 'e' is a vowel; it does not pass the filter and is not yielded by the generator.
  5. The characters that pass the filter ('l', 't', 'c', 'd') are joined by the join function into a new string.
  6. The resulting string is "ltcd", which is the original string "leetcode" without the vowels.
  7. The removeVowels method returns the string "ltcd".

Our example has successfully demonstrated how each character is considered individually, and only non-vowel characters are concatenated to form the final string. The simplicity of the generator expression makes this method both efficient and easy to read.

Python Solution

1class Solution:
2    def removeVowels(self, string: str) -> str:
3        # Initialize a list to store characters that are not vowels
4        non_vowel_chars = []
5
6        # Iterate over each character in the input string
7        for char in string:
8            # Check if the character is not a vowel
9            if char.lower() not in "aeiou":
10                # If it's not a vowel, append it to the list
11                non_vowel_chars.append(char)
12
13        # Join the non-vowel characters back into a string and return it
14        return "".join(non_vowel_chars)
15

Java Solution

1class Solution {
2    // Method to remove all vowels from a given string
3    public String removeVowels(String s) {
4        // Use StringBuilder to build the result string efficiently
5        StringBuilder resultBuilder = new StringBuilder();
6      
7        // Iterate over each character in the string
8        for (int i = 0; i < s.length(); i++) {
9            // Retrieve the current character
10            char currentChar = s.charAt(i);
11          
12            // Check if the current character is not a vowel
13            if (!(currentChar == 'a' || currentChar == 'e' || currentChar == 'i' ||
14                  currentChar == 'o' || currentChar == 'u')) {
15                // If it's not a vowel, append it to the resultBuilder
16                resultBuilder.append(currentChar);
17            }
18        }
19      
20        // Convert the StringBuilder to a String and return it
21        return resultBuilder.toString();
22    }
23}
24

C++ Solution

1class Solution {
2public:
3    // Function to remove vowels from the string
4    string removeVowels(string s) {
5        string result; // Initialize an empty string to store the result
6
7        // Iterate through each character in the input string
8        for (char& c : s) {
9            // Check if the character is not a vowel
10            if (!(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')) {
11                result += c; // If it's not a vowel, add it to the result string
12            }
13        }
14
15        return result; // Return the resultant string without vowels
16    }
17};
18

Typescript Solution

1// This function removes all vowels from a given string
2function removeVowels(s: string): string {
3    // Use a regular expression to find all vowels (both lowercase and uppercase)
4    // in the string and replace them with an empty string
5    return s.replace(/[aeiouAEIOU]/g, '');
6}
7

Time and Space Complexity

Time Complexity

The time complexity of traversing the string and checking each character if it's a vowel or not is O(n), where n is the length of the string. No nested loops or complex operations are involved, so the time complexity is linear with the size of the input string.

Space Complexity

The space complexity is also O(n), primarily due to the space required to build the output string. Since the output string may potentially contain almost all characters from the input string (in the case when the input contains few or no vowels), the space required grows linearly with the input size.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫