Yet Another Substring Reverse
Contest: Codeforces Round 590 (Div. 3)
Difficulty rating: 2200
Tags: bitmasks, dp

You are given a string $$$s$$$ consisting only of first $$$20$$$ lowercase Latin letters ('a', 'b', ..., 't').

Recall that the substring $$$s[l; r]$$$ of the string $$$s$$$ is the string $$$s_l s_{l + 1} \dots s_r$$$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

You can perform the following operation no more than once: choose some substring $$$s[l; r]$$$ and reverse it (i.e. the string $$$s_l s_{l + 1} \dots s_r$$$ becomes $$$s_r s_{r - 1} \dots s_l$$$).

Your goal is to maximize the length of the maximum substring of $$$s$$$ consisting of distinct (i.e. unique) characters.

The string consists of distinct characters if no character in this string appears more than once. For example, strings "abcde", "arctg" and "minecraft" consist of distinct characters but strings "codeforces", "abacaba" do not consist of distinct characters.

Input format:
The only line of the input contains one string $$$s$$$ consisting of no more than $$$10^6$$$ characters 'a', 'b', ..., 't' (first $$$20$$$ lowercase Latin letters).

Output format:
Print one integer — the maximum possible length of the maximum substring of $$$s$$$ consisting of distinct characters after reversing no more than one its substring.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
abacaba

Example output:
3

Example input:
abcdecdf

Example output:
6

Editorial:
First of all, I wanted to offer you one little challenge: I found a solution that I can't break (and I don't sure if it can be broken) and I will be so happy if anyone will give me countertest which will break it. You can see its code below.
Let's notice that we can reduce our problem to the following: find two substrings of the given string that letters in them do not intersect and the total length of these substrings is the maximum possible. Why can we make such a reduction? It is so because our answer consists of at most two non-intersecting parts: one fixed substring and at most one substring that we appended to the first one. We can always append any other substring to the first one by one reverse operation (just look at some examples to understand it).
Let's iterate over all possible substrings of length at most $$$AL$$$ (where $$$AL$$$ is the size of the alphabet) which contain distinct letters. We can do it in $$$O(n AL)$$$. Let the current substring containing distinct letters be $$$s[i; j]$$$. Let's create the bitmask corresponding to this substring: the bit $$$pos$$$ is $$$1$$$ if the $$$pos$$$-th letter of the alphabet is presented in the substring and $$$0$$$ otherwise (letters are $$$0$$$-indexed).
Store all these masks somewhere. Notice that our current problem can be reduced to the following: we have the set of masks and we need to find a pair of masks that they do not intersect and their total number of ones in them is the maximum possible. This reduction is less obvious than the previous one but you also can understand it considering some examples.
So how to solve this problem? We can do it with easy bitmasks dynamic programming! Let $$$dp_{mask}$$$ be the maximum number of ones in some mask that is presented in the given string and it is the submask of $$$mask$$$. How to calculate this dynamic programming? First of all, all values $$$dp_{mask}$$$ for all masks presented in the string are equal to the number of ones in corresponding masks. Let's iterate over all masks from $$$0$$$ to $$$2^{AL} - 1$$$. Let the current mask be $$$mask$$$. Then let's try to update the answer for this mask with the answer for one of its submasks. It is obvious that because of dynamic programming we need to remove at most one bit from our mask to cover all possible submasks that can update our answer. So let's iterate over all bits in $$$mask$$$, let the current bit be $$$pos$$$. If this bit is zero then just skip it. Otherwise update $$$dp_{mask} := max(dp_{mask}, dp_{mask \hat{} 2^{pos}})$$$, where $$$\hat{}$$$ is the xor operation.
After calculating this dynamic programming we can finally calculate the answer. Let's iterate over all masks presented in the string, let the current mask be $$$mask$$$. We can update the answer with the number of ones in $$$mask$$$ plus $$$dp_{mask \hat{} (2^{AL} - 1)}$$$ ($$$mask \hat{} (2^{AL} - 1)$$$ is the completion of $$$mask$$$).
Total complexity: $$$O(n AL + AL 2^{AL})$$$.