Secuencia de Cerradura y Llave#12236
Iniciar sesión

Secuencia de Cerradura y Llave (Editorial)

Autor del Problema:

Imran AKKI

Preparado por:

Imran AKKI

Editado por:

Hasan Saleh (MathModel)

Solución Necesitamos dos extremos iguales y caracteres distintos entre ellos estrictamente. De manera equivalente: encontrar l < r con s_l=s_r tal que la subcadena s[l+1;r-1]=s_{l+1}s_{l+2}...s_{r-1} contenga al menos letras distintas, y entre todos esos pares devolver el que minimice r-l+1.

Observa que para un extremo izquierdo fijo y un carácter fijo c = s_l, si se desplaza hacia la derecha, el número de letras distintas dentro de (l,r) es no decreciente a medida que avanza. Esa monotonía nos permite hacer una búsqueda binaria del valor más pequeño que satisfaga la condición de letras distintas para cada .

Podemos contar las ocurrencias de algún carácter en usando arreglos de frecuencia prefijos sobre las 26 letras minúsculas como , luego para cada letra que aparezca al menos dos veces:

  1. Para cada índice de ocurrencia (ocurrencia izquierda) realizar búsqueda binaria entre las ocurrencias posteriores \text{pos}[c][\text{mid}] para el menor tal que la subcadena intermedia s[i+1;r-1] contenga letras distintas.

  2. Usar para contar letras distintas en esa subcadena intermedia; tan pronto como se encuentren distintas.

  3. Guardar la longitud mínima de subcadena r-i+1 y los extremos correspondientes.

// Autor: Imran AKKI (imranakki)
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lp(i, a, n) for (ll i = a; i < n; i++)
#define MAXN 1000005
#define MOD (ll)(1e9 + 7)
using namespace std;

void solve()
{
    ll n, k; cin >> n >> k;
    string s; cin >> s;

    // ¡Indexación desde 1!
    vector<vector<ll>> pre(26, vector<ll>(n + 2, 0));
    for(ll d = 0; d < 26; d++) {
        for(ll i = 0; i < n; i++) {
            pre[d][i + 1] = pre[d][i] + ((s[i] - 'a') == d);
        }
    }

    vector<ll> pos[26];
    for(ll i = 0; i < n; i++){
        pos[s[i] - 'a'].push_back(i);
    }

    auto can = [&](ll i, ll l) {
        // i y l están indexados desde 0
        if(l - i < k + 1) return false;
        ll distinct = 0;
        for(ll d = 0; d < 26; d++) {
            if(pre[d][l] - pre[d][i + 1] > 0) {
                distinct++;
                if(distinct >= k){
                    return true;
                }
            }
        }
        return false;
    };
    ll bestLen = INT_MAX;
    ll bestI = -1, bestJ = -1;
    for(ll c = 0; c < 26; c++) {
        auto &P = pos[c];
        ll m = P.size();
        if(m < 2) continue;

        for(ll x = 0; x < m - 1; x++) {
            ll i = P[x];
            ll l = x + 1, r = m - 1;
            ll best = -1;
            while(l <= r) {
                ll mid = (l + r) >> 1;
                if(can(i, P[mid])) {
                    best = mid;
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            if(best != -1  && can(i, P[best]) && P[best] - i + 1 < bestLen) {
                bestLen = min(bestLen, P[best] - i + 1);
                bestI = i;
                bestJ = P[best];
            }
        }
    }

    if(bestI != -1) {
        cout << "YES\n";
        cout << bestI + 1 << " " << bestJ + 1 << "\n";
    } else {
        cout << "NO\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t; cin >> t;
    while(t--) solve();
    return 0;
}
C++

Complejidad : \mathcal{O}(n \cdot 26 \cdot \log n)