Challenge: Longest Unique Stretch

Lab C++ Intermediate 20 points

Read a word and print the length of the longest stretch of neighbouring letters with no letter repeated.

Input

One word (lowercase letters only).

Output

One number.

Example

Input

abcabcbb

Output

Sample input available Sample output available

Editor

C++

Hints

Keep a count of each letter inside the window.

If the new letter's count goes above 1, shrink from the left.

Solution explanation

Each letter enters and leaves the window at most once: O(n).

Show solution

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int count[26] = {0};
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right] - 'a']++;
        while (count[s[right] - 'a'] > 1) count[s[left++] - 'a']--;
        best = max(best, right - left + 1);
    }
    cout << best << endl;
    return 0;
}

Output

Answer