Code Implementation

class Solution:
    def removeVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        return ''.join([c for c in s if c not in vowels])
      

class Solution {
public:
    string removeVowels(string s) {
        unordered_set<char> vowels = {'a','e','i','o','u','A','E','I','O','U'};
        string result;
        for (char c : s) {
            if (vowels.find(c) == vowels.end()) {
                result += c;
            }
        }
        return result;
    }
};
      

class Solution {
    public String removeVowels(String s) {
        StringBuilder result = new StringBuilder();
        String vowels = "aeiouAEIOU";
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) == -1) {
                result.append(c);
            }
        }
        return result.toString();
    }
}
      

/**
 * @param {string} s
 * @return {string}
 */
var removeVowels = function(s) {
    const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
    let result = '';
    for (let c of s) {
        if (!vowels.has(c)) {
            result += c;
        }
    }
    return result;
};
      

Problem Description

The problem asks you to remove all vowels from a given string s. A vowel is any of the characters 'a', 'e', 'i', 'o', 'u' (both lowercase and uppercase). You should return the new string after removing all vowels, preserving the order and case of the remaining characters.

• Input: A single string s (can contain uppercase and lowercase letters).
• Output: A string with all vowels removed.
• Constraints: All characters in s are English letters. The solution should process the string efficiently.
• Each vowel should be removed wherever it appears; do not reuse or skip any character.

Thought Process

To solve this problem, the main task is to identify which characters are vowels and filter them out from the original string. The simplest approach is to scan the string character by character and check if each character is a vowel. If it is not a vowel, we keep it; otherwise, we skip it.

Initially, you might think of creating a new string and appending non-vowel characters as you go. To check if a character is a vowel, you can use a collection (like a set or string) containing all vowels for quick lookup.

Brute-force would be to check each character with a series of if statements, but this can be optimized by using a set or string lookup, which is more concise and efficient.

Solution Approach

Here’s a step-by-step breakdown of the solution:

1. Define the set of vowels:
   • Create a collection (like a set or string) containing all vowels, both lowercase and uppercase: 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'.
2. Iterate through the input string:
   • Loop through each character in the input string s.
3. Check for vowels:
   • For each character, check if it is in the set of vowels.
4. Build the result:
   • If the character is not a vowel, append it to a result string or list.
5. Return the result:
   • After the loop, join the collected characters into a single string (if using a list) and return it.

Using a set for vowels is efficient because checking membership in a set is typically O(1).

Example Walkthrough

Let's walk through an example with the input s = "LeetCode":

1. Start with an empty result.
2. Go through each character:
   • 'L' - not a vowel, add to result ("L").
   • 'e' - vowel, skip.
   • 'e' - vowel, skip.
   • 't' - not a vowel, add ("Lt").
   • 'C' - not a vowel, add ("LtC").
   • 'o' - vowel, skip.
   • 'd' - not a vowel, add ("LtCd").
   • 'e' - vowel, skip.
3. Final result: "LtCd"

The algorithm processes each character, skipping vowels and collecting the rest to form the output.

Time and Space Complexity

• Brute-force approach:
  • Checking each character with multiple if statements is O(n), where n is the length of the string.
  • Space complexity is O(n) for the result string.
• Optimized approach (using a set):
  • Still O(n) time complexity, since we look at each character once and set lookup is O(1).
  • Space complexity is O(n) for the result, and O(1) for the set of vowels (since the set size is constant).

Summary

The key to this problem is efficiently identifying and removing vowels from the input string. By using a set for quick vowel lookups and building the result as we process each character, we achieve an elegant and efficient solution. The approach is straightforward, easy to implement in any language, and runs in linear time relative to the size of the input.