Stringforces Codeforces Solution

Stringforces Codeforces Solution

You are given a string ss of length nn. Each character is either one of the first kk lowercase Latin letters or a question mark.

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

Let fifi be the maximum length substring of string ss, which consists entirely of the ii-th Latin letter. A substring of a string is a contiguous subsequence of that string. If the ii-th letter doesn’t appear in a string, then fifi is equal to 00.

The value of a string ss is the minimum value among fifi for all ii from 11 to kk.

What is the maximum value the string can have?Input

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

The second line contains a string ss, consisting of nn characters. Each character is either one of the first kk 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 kk lowercase Latin letters.

Examples

input

10 2
a??ab????b

output

4

input

9 4
?????????

output

2

input

2 3
??

output

0

input

15 3
??b?babbc??b?aa

output

3

input

4 4
cabd

output

1

Note

In the first example the question marks can be replaced in the following way: “aaaababbbb”. f1=4f1=4, f2=4f2=4, thus the answer is 44. Replacing it like this is also possible: “aaaabbbbbb”. That way f1=4f1=4, f2=6f2=6, however, the minimum of them is still 44.

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 fifi is always 00.

Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int,int>
#define F first
#define S second
#define ever (;;)

const int N = 400100;

int n,k,mem[N],cum[N][20],len,vis[N],timer;
char A[N];
string s;

bool canPut(int c,int pos,int len)
{
    for(int i=0;i<k;i++)
    {
        if( i == c )
            continue;

        if( cum[pos+len-1][i] - cum[pos-1][i] )
            return 0;
    }

    return 1;
}

int dp(int i)
{
    if( i == n+1 )
        return 0;

    int &ret = mem[i];
    if( vis[i] == timer )
        return ret;
    vis[i] = timer;

    ret = dp(i+1);

    for(int c=0;c<k;c++)
        if( canPut(c,i,len) && i+len <= n+1 )
            ret = max( ret , dp(i+len)|(1<<c) );

    return ret;
}

bool ok(int mid)
{
    if( mid == 0 )
        return 1;

    timer++;
    len = mid;

    for(int i=n;i>=1;i-=1000)
        dp(i);

    return dp(1) == (1<<k)-1;
}

int main()
{
    scanf("%d%d%s",&n,&k,&A);
    s = A;
    s = '#' + s;

    for(int i=1;i<=n;i++)
    {
        if( s[i] != '?' )
            cum[i][s[i]-'a']++;

        for(int j=0;j<k;j++)
            cum[i][j] += cum[i-1][j];
    }

    int low = 0,high = n;
    while( low < high )
    {
        int mid = (low+high+1)/2;

        if( ok(mid) )
            low = mid;
        else
             high = mid-1;
    }

    printf("%d\n",low);
}

Educational Codeforces Round 111 (Rated for Div. 2)

Leave a Comment