Longest Even Character Substring

Given a string S consisting of only lowercase letters, your task is to find the length of the longest contiguous substring such that every character in the substring appears an even number of times.

Formally, for a given string \( S \), determine the maximum length \( L \) for which there exists a substring \( S[i \ldots j] \) with \( j - i + 1 = L \) where every character has even frequency. If no such substring exists, output 0.

Example:

• For \( S = \texttt{aabbccddeeff} \), the answer is 12 since the whole string satisfies the condition.
• For \( S = \texttt{ababc} \), the longest valid substring has length 4.

The problem can be efficiently solved using bitmasking to track the parity of frequencies. At each index, the current state can be represented as a 26-bit integer, with each bit corresponding to one of the lowercase English letters. Using a dictionary (or map) to store the first occurrence of each state, one can determine the maximum distance between two indices where the same state appears, which yields a substring with even frequency counts for all characters.

inputFormat

The input consists of a single line containing a string S made up of lowercase English letters only.

outputFormat

Output a single integer - the length of the longest contiguous substring where every character appears an even number of times.## sample

aabbccddeeff

12