Find the Longest Substring Containing Vowels in Even Counts

class Solution {
public:
    int longestVowelSubstring(string str) {
        int runningXOR = 0;
        int vowelMap[26] = {0};
        vowelMap['a' - 'a'] = 1;
        vowelMap['e' - 'a'] = 2;
        vowelMap['i' - 'a'] = 4;
        vowelMap['o' - 'a'] = 8;
        vowelMap['u' - 'a'] = 16;
        
        vector<int> firstOccurrence(32, -1);
        int maxSubstringLength = 0;

        for (int idx = 0; idx < str.size(); idx++) {
            runningXOR ^= vowelMap[str[idx] - 'a'];
            if (firstOccurrence[runningXOR] == -1 && runningXOR != 0) firstOccurrence[runningXOR] = idx;

            maxSubstringLength = max(maxSubstringLength, idx - firstOccurrence[runningXOR]);
        }

        return maxSubstringLength;
    }
};

This solution in C++ focuses on finding the longest substring such that the substring contains all vowels (a, e, i, o, u) an even number of times in a given string str.

• Start by mapping each vowel to a unique bit in an integer using a simple hash array vowelMap, which will help in keeping count of each vowel's occurrences using bitwise XOR operation.
• Use an integer runningXOR to keep a running XOR-ed value of the characters processed so far. This approach takes advantage of the fact that XOR-ing a number an even number of times returns the result to zero.
• The array firstOccurrence of size 32 (to handle all possible XOR results from 0 to 31) is utilized to store the first index where each XOR result was found.
• Initialize firstOccurrence with -1 indicating that these XOR results haven't occurred yet.
• Iterate through each character of the string. For each character:
  • Update runningXOR with the XOR of the current character's mapped value.
  • Check if runningXOR is non-zero and its value has not been seen before; mark its first occurrence.
  • For zero runningXOR (indicating all vowels have appeared an even number of times up to the current index), or a previously seen XOR result, calculate the length of the substring using the stored index in firstOccurrence.
  • Keep track of the maximum length of such substrings encountered.
• The result, maxSubstringLength, provides the length of the longest substring where the vowel count is even.

This approach efficiently utilizes bitwise operations for continuous checks and updates, employing an XOR mechanism combined with hash mapping and index storage for optimized substring length calculation.

class Solution {

    public int longestVowelSubstring(String str) {
        int currentXOR = 0;
        int[] vowelIndices = new int[26];
        vowelIndices['a' - 'a'] = 1;
        vowelIndices['e' - 'a'] = 2;
        vowelIndices['i' - 'a'] = 4;
        vowelIndices['o' - 'a'] = 8;
        vowelIndices['u' - 'a'] = 16;
        int[] indicesMap = new int[32];
        for (int i = 0; i < 32; i++) indicesMap[i] = -1;
        int maxLen = 0;
        for (int idx = 0; idx < str.length(); idx++) {
            currentXOR ^= vowelIndices[str.charAt(idx) - 'a'];
            if (indicesMap[currentXOR] == -1 && currentXOR != 0) indicesMap[currentXOR] = idx;
            maxLen = Math.max(maxLen, idx - indicesMap[currentXOR]);
        }
        return maxLen;
    }
}

The provided Java code defines a method to find the length of the longest substring where the count of each vowel (a, e, i, o, u) occurs an even number of times. Here's a breakdown of how the method accomplishes this:

• Initialize currentXOR to track the parity (even or odd count) of vowels encountered so far using XOR operation.
• Define vowelIndices to map each vowel to a unique integer, using bitwise operations to distinguish combinations of even and odd counts.
• Utilize indicesMap to remember the first occurrence of each XOR state.
  • If a particular XOR state is encountered for the first time and isn't the initial state, it is recorded.
  • Recount of a previous XOR state indicates a region between two indices where vowels have been seen an even number of times.
• Iterate through each character of the input string updating the currentXOR.
  • Use XOR to flip the state of the vowel count.
  • Check the indicesMap for the existing XOR state.
  • Update the maximum length (maxLen) of the substring whenever a known XOR state is encountered or update the start index of the XOR state in the map if it's the first time.
• Finally, return maxLen, which represents the length of the longest substring with all vowels in even counts.

This approach capitalizes on the bitwise representation of vowel counts and checks substring validity efficiently through XOR operations. This ensures that only substrings with even counts of all vowels are considered, optimizing the search for the longest valid substring.

class Solution:
    def findMaxLengthSubstr(self, input_str: str) -> int:
        xor_val = 0
        vowel_mask = [0] * 26
        vowel_mask[ord("a") - ord("a")] = 1
        vowel_mask[ord("e") - ord("a")] = 2
        vowel_mask[ord("i") - ord("a")] = 4
        vowel_mask[ord("o") - ord("a")] = 8
        vowel_mask[ord("u") - ord("a")] = 16
        index_map = [-1] * 32
        max_length = 0
        for idx in range(len(input_str)):
            xor_val ^= vowel_mask[ord(input_str[idx]) - ord("a")]
            if index_map[xor_val] == -1 and xor_val != 0:
                index_map[xor_val] = idx
            max_length = max(max_length, idx - index_map[xor_val])
        return max_length

This Python solution aims to solve the problem of finding the longest substring where the count of each vowel (a, e, i, o, u) is even. The solution uses bitwise operations to efficiently track which vowels have even counts at any given point in the string.

• The approach uses an array, vowel_mask, to map each vowel to a corresponding bit position. This allows tracking the evenness of each vowel's count using bitwise XOR operations.
• xor_val tracks the current state of vowel evenness as the string is processed.
• The index_map array stores the first occurrence where each state of xor_val appears, enabling calculation of the length of substrings with even vowel counts.
• As the string is traversed, xor_val is updated for each character. If this state has been seen before, the length of the substring that has even counts of vowels can be calculated using the current index minus the first index where this state occurred.
• max_length is updated continuously to store the size of the longest found substring satisfying the condition.

By leveraging XOR operations and maintaining a state map, the code effectively finds the longest such substring with a linear iteration over the string characters, thus providing an efficient solution in terms of both time and space complexity. In the end, max_length gives the length of the longest substring fulfilling the criteria.