The longest stretch where every letter pairs up
Reported in interviews at (where)
A stretch of a word is some letters that sit side by side in it. Call a stretch even when every letter in it appears an even number of times; a letter that does not appear at all appears 0 times, which is even.
For each word, find the length of its longest even stretch. If no letter can be kept, the answer is 0.
Checking every stretch costs O(n²), too slow for the largest tests.
Input
The first line holds T, the number of tests. Each test is one line holding one word of lowercase letters.
Output
For each test, one line: the length of the longest even stretch of its word.
- Input
3
cabbad
abc
aabbcc- Output
4
0
6
- abba has two a and two b. The whole word has one c and one d.
- Every stretch of at least one letter has some letter just once.
- The whole word is even.
Limits
1 <= T <= 100each word holds 1 to 100000 lettersall the words together hold at most 400000 letters
Hints
Hint 1
Only whether each count is odd or even matters. Keep 26 bits, one per letter, and flip a letter's bit each time you pass it: the bits after each prefix of the word.
Hint 2
A stretch is even exactly when the bits before it and after it are equal. So remember the first position each set of bits was seen at, and the answer is the longest gap between two equal ones.
Where this was reported
- American Express, Technology intern interview, 2021 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
