La conexión perdida de Neru (Editorial)

Solución

Existen solo $8$ cadenas diferentes de longitud $3$ que consisten únicamente en los caracteres "a" y "b".

Vamos a iterar sobre la cadena que Teto quiere obtener como el estribillo común. La denotaremos como $t$.

Ahora, para cada cadena inicial s_i, debemos determinar si puede volverse igual a $t$.

Como para cada cadena se puede realizar como máximo una operación, la cadena s_i se puede transformar en $t$ si y solo si difieren en no más de una posición.

Es decir, debemos contar la cantidad de posiciones en las que s_i y $t$ tienen caracteres diferentes.

• Si esta cantidad es igual a $0$, entonces la cadena ya sirve.

• Si esta cantidad es igual a $1$, entonces podemos cambiar un carácter y obtener $t$.

• Si esta cantidad es mayor que $1$, entonces tal cadena no se puede transformar en $t$.

Para cada una de las $8$ posibles cadenas $t$, contamos la cantidad de cadenas s_i que se pueden hacer iguales a $t$. La respuesta es el máximo entre estos valores.

Ejemplo

En el ejemplo, podemos elegir la cadena "aaa".

Entonces las cadenas:

• "aaa" ya es igual a "aaa";

• "aab" se puede cambiar en la tercera posición;

• "aba" se puede cambiar en la segunda posición;

• "baa" se puede cambiar en la primera posición.

Por lo tanto, se pueden obtener $4$ cadenas iguales.

Complejidad

Iteramos sobre $8$ posibles cadenas objetivo. Para cada una de ellas, recorremos todas las $n$ cadenas y comparamos $3$ caracteres.

Por lo tanto, la complejidad de la solución es O(8 \cdot n \cdot 3), es decir, $O(n)$.

#include <bits/stdc++.h>

using namespace std;

#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int dist(string a, string b) {
    int cnt = 0;

    for (int i = 0; i < 3; i++) {
        if (a[i] != b[i]) cnt++;
    }

    return cnt;
}

void solve() {
    int n;
    cin >> n;

    vector<string> s(n);

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    int ans = 0;

    for (int mask = 0; mask < 8; mask++) {
        string target = "";

        for (int i = 0; i < 3; i++) {
            if (mask & (1 << i)) target += 'b';
            else target += 'a';
        }

        int cnt = 0;

        for (int i = 0; i < n; i++) {
            if (dist(s[i], target) <= 1) {
                cnt++;
            }
        }

        ans = max(ans, cnt);
    }

    cout << ans << endl;
}

signed main() {
    speed;

    solve();

    return 0;
}