Estrategia: Una sola iteración

Intuición

Si un caracter en word aparece consecutivamente k veces (donde k > 1), y Alice comete un error, entonces en la cadena original actual, este caracter podría aparecer 1,2,...,k-1 veces. De manera que tenemos k-1 posibles variaciones.

Para el caso donde k = 1, Alice no cometió ningún error, asi que hay 0 posibilidades, lo que es coherente con la fórmula k - 1.

Por lo tanto, podemos recorrer la cadena una vez: dejemos que la posición de recorrido actual sea l, y supongamos que los caracteres de la palabra a partir de las posiciones [l, r] son iguales, mientras que el carácter de la posición r + 1 es diferente (o no existe). En este caso, aumentamos la respuesta en r - l, y continuamos el recorrido desde la posición r + 1.

Esto implica además que la contribución total del intervalo [l, r] a la respuesta es r - l. Podemos interpretar esto como que la posición l no contribuye a la respuesta, mientras que cada una de las posiciones [l+1,r] contribuye con 1. Por lo tanto, para cualquier posición i de la cadena word (donde i > 0), if word[i - 1] == word[i], podemos aumentar la respuesta en 1.

Implementación

class Solution {
public:
    int possibleStringCount(string word) {
        int n = word.size(), ans = 1;
        for (int i = 1; i < n; ++i) {
            if (word[i - 1] == word[i]) {
                ++ans;
            }
        }
        return ans;
    }
};

Complexity analysis

Supongamos que n representa la longitud de la cadena word.

• Complejidad de tiempo: O(n).
• Complejidad de espacio: O(1).