Problem Brief
Longest Substring with Even Occurrences
NEW GRADOA
Write a function:
def solution(S)
that, given a string S consisting of N lowercase English letters, returns the length of the longest substring in which every letter occurs an even number of times. A substring is defined as a contiguous segment of a string. If no such substring exists, return 0.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range
[1..100,000]; - string
Sconsists only of lowercase letters ('a'-'z').
1Example 1
Input
S = "bdaaadadb"
Output
6
Explanation
Substrings in which every letter occurs an even number of times are "aa", "adad", "daaadad" and "aaadad". The length of the longest of them is 6.
2Example 2
Input
S = "abacb"
Output
0
Explanation
There is no non-empty substring in which every letter occurs an even number of times.
3Example 3
Input
S = "zthtzh"
Output
6
Explanation
Every letter in the whole string occurs an even number of times.