**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Bhavya Rustgi

**Tester:** Ildar Gainullin

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

SIMPLE

**PREREQUISITES**:

None

**PROBLEM**:

You’re given a string S. Consider an integer K and two non-empty subsequences A and B each with length K, such that A=B and the amount of common indices in A and B is at most K-1. You have to find maximum value K for which it’s possible.

**QUICK EXPLANATION**:

Basically the problem asks to find maximum K such that there exist different sets of K indices producing same sub-sequence.

**EXPLANATION**:

If there are two neighboring same letters, then the answer is n-1 as you may choose same sub-sequences except for these letters. If there are no neighboring letters then the answer is not n-1 and thus we may always remove *some* letter so that answer won’t change. This process may be repeated until we obtain the sub-sequence which has some neighboring equal letters and has the same answer as initial sequence. So the answer to the problem is defined by the maximum length of sub-sequence having neighboring equal letters, which is the length of the string minus the minimum distance between some pair of repeated letters.

```
void solve() {
int n;
cin >> n;
string s;
cin >> s;
map<char, int> last;
int ans = 0;
for(int i = 0; i < n; i++) {
if(last.count(s[i])) {
ans = max(ans, n - (i - last[s[i]]));
}
last[s[i]] = i;
}
cout << ans << endl;
}
```

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.