Code : Cases

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

void solve(int n, int c, int k, string &str) {
    int full_mask = (1 << c) - 1;
    vector<bool> is_window_mask(full_mask + 1, false);

    map<int, int> window_elements;
    int mask = 0;
    for (int i = 0; i < min(n, k); i++) {
        int rank = str[i] - 'A';
        window_elements[rank]++;
        // Turn on the rank bit in mask.
        mask |= (1 << rank);
    }

    // First window.
    is_window_mask[mask] = true;
    for (int i = k; i < n; i++) {
        // Remove the oldest element from the window.
        int oldrank = str[i - k] - 'A';
        window_elements[oldrank]--;
        if (window_elements[oldrank] == 0) {
            // All occurrence of this element gone, remove it from mask.
            mask ^= (1 << oldrank);
        }

        // Add incoming element to the window.
        int newrank = str[i] - 'A';
        window_elements[newrank]++;
        // Turn on this bit in mask.
        mask |= (1 << newrank);

        is_window_mask[mask] = true;
    }
    // Last element should always be included.
    int lastrank = str[n - 1] - 'A';
    is_window_mask[1 << lastrank] = true;

    // Now, we just need to find a mask whose intersection with all window
    // masks is non zero.
    int ans = c;
    for (int guess = 0; guess <= full_mask; guess++) {
        bool bad = false;
        for (int mask = 0; mask <= full_mask; mask++) {
            if (!is_window_mask[mask]) {
                continue;
            }
            // The bitwise AND should preserve atleast one set bit of mask.
            if ((mask & guess) == 0) {
                bad = true;
                break;
            }
        }
        if (!bad) {
            ans = min(ans, __builtin_popcount(guess));
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n, c, k;
        cin >> n >> c >> k;

        string str;
        cin >> str;

        solve(n, c, k, str);
    }
}

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

void solve(int n, int c, int k, string &str) {
    int full_mask = (1 << c) - 1;
    vector<bool> is_window_mask(full_mask + 1, false);

    map<int, int> window_elements;
    int mask = 0;
    for (int i = 0; i < min(n, k); i++) {
        int rank = str[i] - 'A';
        window_elements[rank]++;
        // Turn on the rank bit in mask.
        mask |= (1 << rank);
    }

    // First window.
    is_window_mask[mask] = true;
    for (int i = k; i < n; i++) {
        // Remove the oldest element from the window.
        int oldrank = str[i - k] - 'A';
        window_elements[oldrank]--;
        if (window_elements[oldrank] == 0) {
            // All occurrence of this element gone, remove it from mask.
            mask ^= (1 << oldrank);
        }

        // Add incoming element to the window.
        int newrank = str[i] - 'A';
        window_elements[newrank]++;
        // Turn on this bit in mask.
        mask |= (1 << newrank);

        is_window_mask[mask] = true;
    }
    // Last element should always be included.
    int lastrank = str[n - 1] - 'A';
    is_window_mask[1 << lastrank] = true;

    // Now, we just need to find a mask whose intersection with all window
    // masks is non zero.
    int ans = c;

    // Let's count all bad masks.
    vector<int> bad(full_mask + 1, false);
    for (int mask = 0; mask <= full_mask; mask++) {
        if (!is_window_mask[mask]) {
            continue;
        }

        int flipped = mask ^ full_mask;
        // Iterate over all subsets of flipped and mark it as bad.
        bad[flipped] = true;
        for (int submask = (flipped - 1) & flipped; submask > 0;
             submask = (submask - 1) & flipped) {
            bad[submask] = true;
        }
    }
    for (int guess = 1; guess <= full_mask; guess++) {
        if (!bad[guess]) {
            ans = min(ans, __builtin_popcount(guess));
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n, c, k;
        cin >> n >> c >> k;

        string str;
        cin >> str;

        solve(n, c, k, str);
    }
}

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

void solve(int n, int c, int k, string &str) {
    int full_mask = (1 << c) - 1;
    vector<bool> is_window_mask(full_mask + 1, false);

    map<int, int> window_elements;
    int mask = 0;
    for (int i = 0; i < min(n, k); i++) {
        int rank = str[i] - 'A';
        window_elements[rank]++;
        // Turn on the rank bit in mask.
        mask |= (1 << rank);
    }

    // First window.
    is_window_mask[mask] = true;
    for (int i = k; i < n; i++) {
        // Remove the oldest element from the window.
        int oldrank = str[i - k] - 'A';
        window_elements[oldrank]--;
        if (window_elements[oldrank] == 0) {
            // All occurrence of this element gone, remove it from mask.
            mask ^= (1 << oldrank);
        }

        // Add incoming element to the window.
        int newrank = str[i] - 'A';
        window_elements[newrank]++;
        // Turn on this bit in mask.
        mask |= (1 << newrank);

        is_window_mask[mask] = true;
    }
    // Last element should always be included.
    int lastrank = str[n - 1] - 'A';
    is_window_mask[1 << lastrank] = true;

    // Now, we just need to find a mask whose intersection with all window
    // masks is non zero.

    // Let's count all bad masks.
    vector<int> bad(full_mask + 1, false);
    for (int mask = 0; mask <= full_mask; mask++) {
        if (!is_window_mask[mask]) {
            continue;
        }

        int flipped = mask ^ full_mask;
        bad[flipped] = true;
    }

    // Iterate over all bad subsets in decreasing order of popcount and offload
    // the responsibility to the lower level.
    for (int cnt = c; cnt >= 0; cnt--) {
        for (int mask = 0; mask <= full_mask; mask++) {
            if (__builtin_popcount(mask) != cnt || !bad[mask]) {
                continue;
            }

            for (int i = 0; i < c; i++) {
                // If i-th bit is set, offload the responsibility by unsetting
                // it.
                if ((1 << i) & mask) {
                    bad[mask ^ (1 << i)] = true;
                }
            }
        }
    }

    int ans = c;
    for (int guess = 1; guess <= full_mask; guess++) {
        if (!bad[guess]) {
            ans = min(ans, __builtin_popcount(guess));
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n, c, k;
        cin >> n >> c >> k;

        string str;
        cin >> str;

        solve(n, c, k, str);
    }
}

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

void solve(int n, int c, int k, string &str) {
    int full_mask = (1 << c) - 1;
    vector<bool> is_window_mask(full_mask + 1, false);

    map<int, int> window_elements;
    int mask = 0;
    for (int i = 0; i < min(n, k); i++) {
        int rank = str[i] - 'A';
        window_elements[rank]++;
        // Turn on the rank bit in mask.
        mask |= (1 << rank);
    }

    // First window.
    is_window_mask[mask] = true;
    for (int i = k; i < n; i++) {
        // Remove the oldest element from the window.
        int oldrank = str[i - k] - 'A';
        window_elements[oldrank]--;
        if (window_elements[oldrank] == 0) {
            // All occurrence of this element gone, remove it from mask.
            mask ^= (1 << oldrank);
        }

        // Add incoming element to the window.
        int newrank = str[i] - 'A';
        window_elements[newrank]++;
        // Turn on this bit in mask.
        mask |= (1 << newrank);

        is_window_mask[mask] = true;
    }
    // Last element should always be included.
    int lastrank = str[n - 1] - 'A';
    is_window_mask[1 << lastrank] = true;

    // Now, we just need to find a mask whose intersection with all window
    // masks is non zero.

    // Let's count all bad masks.
    vector<int> bad(full_mask + 1, false);
    for (int mask = 0; mask <= full_mask; mask++) {
        if (!is_window_mask[mask]) {
            continue;
        }

        int flipped = mask ^ full_mask;
        bad[flipped] = true;
    }

    // Iterate over all bad subsets in decreasing order of popcount and offload
    // the responsibility to the lower level.
    for (int mask = full_mask; mask >= 0; mask--) {
        for (int i = 0; i < c; i++) {
            if (!bad[mask]) {
                continue;
            }
            // If i-th bit is set, offload the responsibility by unsetting
            // it.
            //
            // By the time a mask is processed, all its super masks have been
            // processed.
            if ((1 << i) & mask) {
                bad[mask ^ (1 << i)] = true;
            }
        }
    }

    int ans = c;
    for (int guess = 1; guess <= full_mask; guess++) {
        if (!bad[guess]) {
            ans = min(ans, __builtin_popcount(guess));
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n, c, k;
        cin >> n >> c >> k;

        string str;
        cin >> str;

        solve(n, c, k, str);
    }
}