Stringforces

time limit per test: 3 seconds
memory limit per test: 256 megabytes

Articles

You are given a string $s$ of length $n$ . Each character is either one of the first $k$ lowercase Latin letters or a question mark.

You are asked to replace every question mark with one of the first $k$ lowercase Latin letters in such a way that the following value is maximized.

Let $f_i$ be the maximum length substring of string $s$ , which consists entirely of the $i$ -th Latin letter. A substring of a string is a contiguous subsequence of that string. If the $i$ -th letter doesn’t appear in a string, then $f_i$ is equal to $0$ .

The value of a string $s$ is the minimum value among $f_i$ for all $i$ from $1$ to $k$ .

What is the maximum value the string can have?

Input

The first line contains two integers $n$ and $k (1≤n≤2⋅105; 1≤k≤17)$ — the length of the string and the number of first Latin letters used.

The second line contains a string $s$ , consisting of $n$ characters. Each character is either one of the first $k$ lowercase Latin letters or a question mark.

Output

Print a single integer — the maximum value of the string after every question mark is replaced with one of the first $k$ lowercase Latin letters.

Examples

input

1 2	10 2 a??ab????b

output

input

1 2	9 4 ?????????

output

input

1
2

2 3
??

output

input

1 2	15 3 ??b?babbc??b?aa

output

input

1
2

4 4
cabd

output

Note

In the first example the question marks can be replaced in the following way: $"aaaababbbb"$ . $f_1=4, f_2=4$ , thus the answer is $4$ . Replacing it like this is also possible: $"aaaabbbbbb"$ . That way $f_1=4, f_2=6$ , however, the minimum of them is still $4$ .

In the second example one of the possible strings is $"aabbccdda"$ .

In the third example at least one letter won’t appear in the string, thus, the minimum of values fi is always $0$ .

Tutorial

code

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5+1;
int suf[maxn][18], dp[1<<17];
int n, m;
string s;

bool check(int len) {
    for(int i = 1; i <= m; ++ i) {
        suf[n][i] = n+1;
    }
    int k = 0, kk = 0, id = -1, kkk = 0;
    for(int i = n; i >= 1; -- i) {
        for(int j = 1; j <= m; ++ j) {
            suf[i-1][j] = suf[i][j];
        }
        if (id == -1 || s[i-1] == '?' || s[i-1] - 'a' + 1 == id) {
            if (s[i-1] == '?') {
                kk ++;
                if (i == n || s[i] == '?') {
                    if (++ kkk >= len) {
                        for(int j = 1; j <= m; ++ j) {
                            suf[i-1][j] = i + len - 1;
                        }
                    }
                }
                else kkk = 1;
            }
            else {
                kkk = 0;
                if (++ k == 1) {
                    id = s[i-1] - 'a' + 1;
                }
            }
            if (id != -1 && k + kk >= len) {
                suf[i-1][id] = i + len - 1;
            }
        }
        else {
            k = 1;
            kk = kkk;
            kkk = 0;
            id = s[i-1] - 'a' + 1;
            if (k + kk >= len) {
                suf[i-1][id] = i + len -1;
            }
        }
    }
    // for(int i = 1; i <= n; ++ i) {
    //     cout << suf[i-1][4] << " \n"[i==n];
    // }
    int inf = n+1, ans = inf;
    for(int i = 1; i < (1<<m); ++ i) {
        dp[i] = n+1;
    }
    for(int i = 0; i < (1<<m); ++ i) {
        if (dp[i] == inf) continue;
        int cnt = 0;
        for(int j = 0; j < m; ++ j) {
            if (i >> j & 1) continue;
            cnt ++;
            dp[i+(1<<j)] = min(dp[i+(1<<j)], suf[dp[i]][j+1]);
        }
        if (cnt == 0) ans = min(dp[i], ans);
    }
    return ans < inf;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s;
    int l = 1, r = n + 1;
    // cout << check(3) << "\n";
    while(l < r) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid;
    }
    cout << l - 1 << "\n";
    return 0;
}