POTD Leetcode : 1371. Find the Longest Substring Containing Vowels in Even Counts

When tackling string manipulation problems, one interesting challenge involves finding the longest substring where vowels appear an even number of times. This problem, sometimes referred to as LeetCode Problem 1371, can be solved efficiently using a bitmasking technique.

Let’s dive into a step-by-step guide on how to approach and solve this problem using JavaScript.

---

Problem Statement:

Given a string s, you are asked to find the length of the longest substring that contains each vowel (a, e, i, o, u) an even number of times.

For example, if the input is:

s = "eleetminicoworoep"

The output should be 13 because the longest substring where all vowels appear an even number of times is "leetminicoworo", which has a length of 13.

---

Solution Approach:

The key to solving this problem efficiently lies in using bitmasking. We can track the count of each vowel using bits in a bitmask. Each vowel is represented by a specific bit, and toggling that bit helps us determine whether the count of that vowel is currently odd or even.

Here’s how we can break down the solution:

1. Map vowels to bits: We will use a bitmask with 5 bits to track whether each vowel (a, e, i, o, u) has appeared an even number of times or not. Each bit corresponds to one vowel:

• a: 1st bit (position 0)
• e: 2nd bit (position 1)
• i: 3rd bit (position 2)
• o: 4th bit (position 3)
• u: 5th bit (position 4)

1. Toggle bits with XOR: As we traverse the string, we toggle the corresponding bit in the bitmask whenever we encounter a vowel. This way, we keep track of whether each vowel’s count is odd or even at any point in the string.
2. Track previous states: We use a map (or hash table) to store the first occurrence of each bitmask state. If the bitmask state repeats, it means all vowels between those two points appear an even number of times, and we calculate the length of that substring.
3. Calculate the result: By keeping track of the maximum length of substrings that satisfy the condition (vowels in even counts), we can find the solution.

---

JavaScript Solution:

Here’s the code implementation based on the above explanation:

function findTheLongestSubstring(s) {
    // Map to store the first occurrence of each bitmask state
    const maskMap = new Map();
    maskMap.set(0, -1);  // Initial state before any characters, bitmask 0 at index -1

    let mask = 0;  // The bitmask that tracks the state of vowels
    let maxLength = 0;  // To store the length of the longest valid substring

    for (let i = 0; i < s.length; i++) {
        // Update the bitmask for the current character
        switch (s[i]) {
            case 'a': mask ^= 1 << 0; break;
            case 'e': mask ^= 1 << 1; break;
            case 'i': mask ^= 1 << 2; break;
            case 'o': mask ^= 1 << 3; break;
            case 'u': mask ^= 1 << 4; break;
        }

        // If this bitmask state has been seen before, calculate the substring length
        if (maskMap.has(mask)) {
            maxLength = Math.max(maxLength, i - maskMap.get(mask));
        } else {
            // Store the first occurrence of this bitmask state
            maskMap.set(mask, i);
        }
    }

    return maxLength;
}

// Example usage
const input = "eleetminicoworoep";
console.log(findTheLongestSubstring(input));  // Output: 13

---

Explanation of the Code:

• Bitmasking vowels: Each vowel is associated with a bit in the bitmask (represented as a 5-bit number). Whenever we encounter a vowel, we use XOR (^) to toggle the corresponding bit. For instance, encountering an a toggles the first bit, while encountering an e toggles the second bit, and so on.
• Tracking states: A map (maskMap) stores the first occurrence of each bitmask state. The idea is that if the same state is encountered twice, the substring between these two points must have an even number of all vowels.
• Calculating the result: At each step, we check if the current bitmask state has been seen before. If it has, we calculate the length of the substring between the first occurrence and the current position. The longest such substring is stored in maxLength.

---

Time Complexity:

This solution runs in O(n) time, where n is the length of the string. Since we only need to traverse the string once and maintain a constant amount of extra space (the bitmask and map), this approach is highly efficient.

---

Conclusion:

Using bitmasking for problems that involve counting occurrences in binary terms (like odd and even counts) can provide significant performance improvements. In this case, it allows us to solve the problem of finding the longest substring containing vowels in even counts in linear time, making it a powerful approach for string manipulation problems.

Try implementing this solution in your next coding challenge or interview preparation, and enjoy solving more problems with the power of bitmasking!

---

Feel free to reach out in the comments if you have any questions or improvements to the solution!