SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem requires finding the longest substring in a given string s such that each vowel ('a', 'e', 'i', 'o', 'u') appears an even number of times. The string may contain both vowels and consonants, and we need to return the length of the longest such substring.

Intuition

The idea is to keep track of the number of times each vowel appears using a bitmask. If the current bitmask has been seen before, it means the substring between the two occurrences of the bitmask has an even number of vowels. Using a hashmap (or equivalent structure) to store the first occurrence of each unique bitmask helps in computing the longest valid substring.

Approach

1. Use a bitmask to track the parity (odd or even) of occurrences of vowels ('a', 'e', 'i', 'o', 'u'). Each vowel is assigned a specific bit in the mask.
2. Traverse the string and for each character:
   • If it is a vowel, toggle the corresponding bit in the bitmask.
   • Check if this bitmask has been seen before:
     • If yes, the substring between the first occurrence of the bitmask and the current position has an even number of vowels. Update the maximum length accordingly.
     • If no, store the current index for this bitmask.
3. Finally, return the length of the longest valid substring.

Complexity

Time Complexity:

O(n), where n is the length of the string. We traverse the string once, and all operations (bitmasking and hashmap operations) are constant time.

Space Complexity:

O(1) for storing the bitmask and O(n) for the hashmap to store bitmask indices

Code

C++

class Solution {
public:
    int findTheLongestSubstring(string s) {
        unordered_map<char, int> vowels = { {'a', 0}, {'e', 1}, {'i', 2}, {'o', 3}, {'u', 4} };
        unordered_map<int, int> bitmap;
        bitmap[0] = -1;
        int maxLen = 0, curr = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s[i];
            if (vowels.find(ch) != vowels.end()) {
                curr ^= (1 << vowels[ch]);
            }
            if (bitmap.find(curr) == bitmap.end()) {
                bitmap[curr] = i;
            } else {
                maxLen = max(maxLen, i - bitmap[curr]);
            }
        }
        return maxLen;
    }
};

Python

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        vowels = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
        bitmap = {0: -1}
        max_len = 0
        curr = 0

        for i, ch in enumerate(s):
            if ch in vowels:
                curr ^= (1 << vowels[ch])
            if curr not in bitmap:
                bitmap[curr] = i
            else:
                max_len = max(max_len, i - bitmap[curr])

        return max_len

Java

class Solution {
    public int findTheLongestSubstring(String s) {
        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);

        HashMap<Integer, Integer> bitmap = new HashMap<>();
        bitmap.put(0, -1);
        int maxLen = 0, curr = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (vowels.containsKey(ch)) {
                curr ^= (1 << vowels.get(ch));
            }
            if (!bitmap.containsKey(curr)) {
                bitmap.put(curr, i);
            } else {
                maxLen = Math.max(maxLen, i - bitmap.get(curr));
            }
        }
        return maxLen;
    }
}

JavaScript

var findTheLongestSubstring = function (s) {
    const vowels = { 'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4 };
    const isVowel = (ch) => {
        return vowels[ch] !== undefined;
    }

    let max = 0;
    let bitmap = { 0: -1 };
    let curr = 0;

    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (isVowel(ch)) {
            // flip this bit
            curr ^= (1 << vowels[ch]);
            if (bitmap[curr] === undefined) {
                bitmap[curr] = i;
                continue;
            }
        }
        max = Math.max(max, i - bitmap[curr]);
    }

    return max;
};