Find the Longest Substring Containing Vowels in Even Counts

This is the Medium level question of Leetcode Link.

Problem Description

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

• 1 <= s.length <= 5 x 10^5

• s contains only lowercase English letters.

Intuition

The problem asks us to find the longest substring where each vowel appears an even number of times. To solve this, the key observation is that we can represent the number of vowels in the substring using a "mask" or a bitmask. Each vowel ('a', 'e', 'i', 'o', 'u') can be assigned a unique bit in a 5-bit integer (since there are 5 vowels), where the state of each bit represents whether the vowel has appeared an odd or even number of times in the substring.

Approach

1. Mask Representation:

   • We'll use an integer mask where each bit represents whether a vowel has appeared an odd (1) or even (0) number of times. The bit positions are as follows:

     • 'a' → 1st bit

     • 'e' → 2nd bit

     • 'i' → 3rd bit

     • 'o' → 4th bit

     • 'u' → 5th bit

   • Initially, mask = 0, indicating that no vowel has been encountered, and thus all vowels have appeared an even number of times (0 times is considered even).

2. Iterating Over the String:

   • As we iterate through the string, for each vowel we encounter, we toggle the corresponding bit in the mask. For example, encountering 'a' would toggle the first bit, and encountering 'e' would toggle the second bit, and so on.

   • If we encounter the same mask value at two different positions, it means that the substring between those two positions has balanced the number of vowels, i.e., all vowels in that substring appear an even number of times.

3. Using a Map to Track the First Occurrence of a Mask:

   • We use a map to store the first index at which each mask value occurs. If we encounter the same mask value again at a later index, it implies that the substring between these two indices has balanced vowels.

   • The key insight is that when the same mask reappears, the substring between the previous and the current index must have all vowels appearing an even number of times.

4. Updating the Maximum Length:

   • For each character, after updating the mask, we check if this mask has been seen before:

     • If it has been seen before, calculate the length of the substring between the first occurrence of this mask and the current index, and update the maximum length accordingly.

     • If it has not been seen, store the current index for this mask in the map.

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. We iterate over the string once, and each operation (mask update, map lookup, and insertion) takes constant time O(1).

Space Complexity

• Space Complexity: O(1), as the map can store at most 32 different mask values (since there are 5 vowels, leading to 2^5 = 32 possible combinations of odd/even vowel counts). This makes the space usage constant with respect to the input size.

Code

class Solution {
    public int findTheLongestSubstring(String s) {
        if(s.length() < 2)
            return 0;

        int mask = 0;
        int max = -1;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);  // To handle the case when a balanced substring starts from the beginning

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // Update the mask if the character is a vowel
            if (isVowel(c)) {
                if (c == 'a') mask ^= 1;
                else if (c == 'e') mask ^= 2;
                else if (c == 'i') mask ^= 4;
                else if (c == 'o') mask ^= 8;
                else if (c == 'u') mask ^= 16;
            }

            // If the mask was seen before, calculate the length of the balanced substring
            if (!map.containsKey(mask)) {
                map.put(mask, i);  // Store the first occurrence of this mask
            } else {
                max = Math.max(max, i - map.get(mask));
            }
        }

        return max;
    }

    public boolean isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}

If you like the solution, please like the blog and give your valuable insights in the comments.

If you like this blog, please do like it.

Check out my Portfolio website for connecting with me or just to say Hi !!.