Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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

Example 3:

1
2
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.

Solution

Method 1 - Use Hashmap and Bitmask

To solve this problem, we can use a bit-manipulation approach combined with a hash map to efficiently find the longest substring where each vowel appears an even number of times.

Here is the approach:

  1. Bitmask Representation
    • Use a bitmask to keep track of the parity (odd/even count) of each vowel.
    • Each bit in the bitmask will represent whether the count of a particular vowel is odd (1) or even (0).
    • For instance, the bitmask for vowels a, e, i, o, u could be represented with 5 bits, where each bit position could be toggled to indicate the occurrence of the respective vowel.
  2. HashMap to Track First Occurrences
    • Use a hashMap to store the first occurrence of each bitmask state.
    • This helps in calculating the length of substrings efficiently whenever we revisit the same bitmask state.
  3. Iterate Through the String
    • While iterating through the string, update the bitmask based on the vowels encountered.
    • Check the current state of the bitmask in the hashMap to determine the length of the longest valid substring ending at the current index.

So here is how it works:

  • 1 State has 5 bits, each bits to indicate if the corresponding vowel have even count or not.
  • When current index have a vowel character, we use bitwise xor to toggle the bit value. bitmask ^= (1 « digit);
  • For the substring between two index have identical state, then all vowels’s count are even number.
    • For eg. if from [0 - i], we have even number of ‘a’, and from [0 - j], if we have even number of ‘a’ again, then the substring between i and j will have even number of ‘a’ as well. This would be the same if [0 - i] and [0 - j] both have odd number of ‘a’.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    public int findTheLongestSubstring(String s) {
        // Map to store the first occurrence of each bitmask
        HashMap<Integer, Integer> stateToIndex = new HashMap<>();
        stateToIndex.put(0, -1); // Initialize to handle the case where the
                                 // entire substring is valid

        int maxLen = 0;
        int bitmask = 0;
        // Vowel positions mapping to their respective bit positions
        HashMap<Character, Integer> vowels = new HashMap<>();
        vowels.put('a', 0);
        vowels.put('e', 1);
        vowels.put('i', 2);
        vowels.put('o', 3);
        vowels.put('u', 4);

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (vowels.containsKey(ch)) {
                // Toggle the bit at the vowel's position
                bitmask ^= (1 << vowels.get(ch));
            }
            // Store the first occurrence of this bitmask state if absent
			stateToIndex.putIfAbsent(bitmask, i); 
			// Calculate the length of the current valid substring
			maxLen = Math.max(maxLen, i - stateToIndex.get(bitmask));
        }

        return maxLen;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution(object):
    def findTheLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # HashMap to store the first occurrence of each bitmask
        state_to_index = {0: -1}
        max_len = 0
        bitmask = 0

        # Map vowels to their respective bit positions
        vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}

        for i, char in enumerate(s):
            if char in vowels:
                # Toggle the bit at the vowel's position
                bitmask ^= 1 << vowels[char]

            if bitmask in state_to_index:
                # Calculate the length of the current valid substring
                max_len = max(max_len, i - state_to_index[bitmask])
            else:
                # Store the first occurrence of this bitmask state
                state_to_index[bitmask] = i

        return max_len

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. We traverse the string once, and each operation within the loop is O(1).
  • 🧺 Space complexity: O(1), O(2^5) since the bitmask can have 32 different states (since there are 5 vowels, each can be either odd or even).

Dry Run

Initialization
  • stateToIndex: {0: -1} (We initialize with a bitmask of 0 mapped to -1 to handle cases where the entire substring from the beginning is valid.)
  • maxLen: 0 (Tracks the length of the longest valid substring found so far.)
  • bitmask: 0 (Tracks the current state of the vowel parities.)

Vowel Bit Position Mapping:

  • 'a' -> Bit 0
  • 'e' -> Bit 1
  • 'i' -> Bit 2
  • 'o' -> Bit 3
  • 'u' -> Bit 4
Iteration Through the string
  • Index 0: 'e'
    • Bitmask before toggle: 00000
    • Toggle bit for ’e’ (bit 1): bitmask ^= (1 << 1) -> 00010 ⇨ bitmask: 2
    • Since 2 is not in stateToIndex, add {2: 0}.
    • stateToIndex: {0: -1, 2: 0}
  • Index 1: 'l'
    • Bitmask remains 00010 (no change) ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(0, 1 - 0) = 1.
  • Index 2: 'e'
    • Bitmask before toggle: 00010
    • Toggle bit for ’e’ (bit 1): bitmask ^= (1 << 1) -> 00000 ⇨ bitmask: 0
    • Found bitmask 0 in stateToIndex:
    • maxLen is updated to max(1, 2 - (-1)) = 3.
  • Index 3: 'e'
    • Bitmask before toggle: 00000
    • Toggle bit for ’e’ (bit 1): bitmask ^= (1 << 1) -> 00010 ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(3, 3 - 0) = 3.
  • Index 4: 't'
    • Bitmask remains 00010 (no change) ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(3, 4 - 0) = 4.
  • Index 5: 'm'
    • Bitmask remains 00010 (no change) ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(4, 5 - 0) = 5.
  • Index 6: 'i'
    • Bitmask before toggle: 00010
    • Toggle bit for ‘i’ (bit 2): bitmask ^= (1 << 2) -> 00110 ⇨ bitmask: 6
    • Since 6 is not in stateToIndex, add {6: 6}.
    • stateToIndex: {0: -1, 2: 0, 6: 6}
  • Index 7: 'n'
    • Bitmask remains 00110 (no change) ⇨ bitmask: 6
    • Found bitmask 6 in stateToIndex
    • maxLen remains 5.
  • Index 8: 'i'
    • Bitmask before toggle: 00110
    • Toggle bit for ‘i’ (bit 2): bitmask ^= (1 << 2) -> 00010 ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(5, 8 - 0) = 8.
  • Index 9: 'c'
    • Bitmask remains 00010 (no change) ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(8, 9 - 0) = 9.
  • Index 10: 'o'
    • Bitmask before toggle: 00010
    • Toggle bit for ‘o’ (bit 3): bitmask ^= (1 << 3) -> 01010 ⇨ bitmask: 10
    • Since 10 is not in stateToIndex, add {10: 10}.
    • stateToIndex: {0: -1, 2: 0, 6: 6, 10: 10}
  • Index 11: 'w'
    • Bitmask remains 01010 (no change) ⇨ bitmask: 10
    • Found bitmask 10 in stateToIndex
    • maxLen remains 9.
  • Index 12: 'o'
    • Bitmask before toggle: 01010
    • Toggle bit for ‘o’ (bit 3): bitmask ^= (1 << 3) -> 00010 ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(9, 12 - 0) = 12.
  • Index 13: 'r'
    • Bitmask remains 00010 (no change) ⇨ bitmask: 2
    • Found bitmask 2 in stateToIndex:
    • maxLen is updated to max(12, 13 - 0) = 13.
  • Index 14: 'o'
    • Bitmask before toggle: 00010
    • Toggle bit for ‘o’ (bit 3): bitmask ^= (1 << 3) -> 01010 ⇨ bitmask: 10
    • Found bitmask 10 in stateToIndex
    • maxLen remains 13.
  • Index 15: 'e'
    • Bitmask before toggle: 01010
    • Toggle bit for ’e’ (bit 1): bitmask ^= (1 << 1) -> 01000 ⇨ bitmask: 8
    • Since 8 is not in stateToIndex, add {8: 15}.
    • stateToIndex: {0: -1, 2: 0, 6: 6, 8: 15, 10: 10}
  • Index 16: 'p'
    • Bitmask remains 01000 (no change) ⇨ bitmask: 8
    • Found bitmask 8 in stateToIndex
    • maxLen remains 13.