#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <random>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 100 + 10;
const ll INF = 2e17;

int brute_force(int n, int k, string s) {
    for(int i = 0; i < n; i++) {
        vector<int> c(26, 0);
        int cnt = 0;
        for(int j = i; j < n; j++) {
            if(s[j] != '?') {
                c[s[j] - 'a']++;
            }
            else {
                cnt++;
            }

            int tmp = cnt;
            bool ok = true;
            for(int l = 0; l < 26; l++) {
                if(c[l] < k) {
                    if(tmp >= k - c[l]) {
                        tmp -= (k - c[l]);
                    }
                    else {
                        ok = false;
                        break;
                    }
                }
                else if(c[l] > k) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                return i + 1;
            }
        }
    }
    return -1;
}

int real_solution(int n, int k, string s) {
    multiset<int> ms;
    for(int i = 0; i < 26; i++) {
        ms.insert(0);
    }
    vector<int> cnt(26, 0);
    int i = 0, j = 0;
    int question_marks = 0;
    int chars = 0;
    while(j < n) {
        if(*ms.begin() <= k and *ms.rbegin() <= k) {
            if(s[j] == '?') {
                question_marks++;
            }
            else {
                chars++;
                ms.erase(ms.find(cnt[s[j] - 'a']));
                cnt[s[j] - 'a']++;
                ms.insert(cnt[s[j] - 'a']);
            }
            j++;
            if(chars + question_marks == 26 * k) {
                return i + 1;
            }
        }
        else {
            if(s[i] == '?') {
                question_marks--;
            }
            else {
                chars--;
                ms.erase(ms.find(cnt[s[i] - 'a']));
                cnt[s[i] - 'a']--;
                ms.insert(cnt[s[i] - 'a']);
            }
            i++;
            if(chars + question_marks == 26 * k) {
                return i;
            }
        }
    }
    return -1;
}

int rand_int(int A, int B) {
    return A + rand() % (B - A + 1);
}
int main() {

    srand(time(nullptr));

    for(int i = 0; i < 1000; i++) {
        int n = rand_int(1, 100);
        int k = rand_int(1, 5);
        string s = "";

        for(int j = 0; j < n; j++) {
            int c = rand_int(0, 26);
            if(c == 26) {
                s += "?";
            }
            else {
                s += (c + 'a');
            }
        }


        if(brute_force(n, k, s) == real_solution(n, k, s)) {
            cout << "Test case #" << i << " passed!" << endl;
        }
        else {
            cout << "FAILURE: " << endl;
            cout << n << " " << k << endl;
            cout << s << endl;
        }
    }


    return 0;
}