O problema "Complete the Word" exige que, dada uma string com letras maiúsculas ou '?' (representando letras desconhecidas), dteermine se é possível substituir os '?' por letras para que a string contenha um substring de comprimento 26 com cada letra do alfabeto aparecendo exatamente uma vez. A técnica de janela deslizante é eficaz para percorreer a string e verificar janelas de tamanho fixo.

Especificação de Entrada e Saída

Entrada: Uma string s (1 ≤ |s| ≤ 50 000) contendo letras maiúsculas ('A'-'Z') e '?'.

Saída: Se não for possível, imprima -1. Caso contrário, imprima uma string válida com todos os '?' substituídos.

Exemplos

Entrada:
ABC??FGHIJK???OPQR?TUVWXY?

Saída:
ABCDEFGHIJKLMNOPQRZTUVWXYS

Entrada:
WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

Saída:
-1

Entrada:
??????????????????????????

Saída:
MNBVCXZLKJHGFDSAQPWOEIRUYT

Entrada:
AABCDEFGHIJKLMNOPQRSTUVW??M

Saída:
-1

Solução com Técnica de Janela Deslizante

A abordagem consiste em percorrer a string com uma janela deslizante de tamanho 26. Para cada janela, contamos as letras presentes e os '?'. Se a soma de letras únicas (cada uma aparecendo exatamente uma vez) e '?' for igual a 26, a janela é válida. Então, substituímos os '?' pelas letras do alfabeto que ainda não estão presentes na janela. Os '?' restantes fora da janela podem ser preenchidos com qualquer letra, como 'A'.

Implemantação em C++

#include <cstdio>
#include <cstring>

const int MAX_TAM = 50005;
char entrada[MAX_TAM];
int contador[26];

int main() {
    while (scanf("%s", entrada) != EOF) {
        bool encontrado = false;
        int tamanho = strlen(entrada);
        if (tamanho < 26) {
            printf("-1\n");
            continue;
        }

        for (int i = 0; i <= tamanho - 26 && !encontrado; i++) {
            int letrasUnicas = 0, perguntas = 0;
            memset(contador, 0, sizeof(contador));

            for (int j = i; j < i + 26; j++) {
                if (entrada[j] >= 'A' && entrada[j] <= 'Z') {
                    contador[entrada[j] - 'A']++;
                } else {
                    perguntas++;
                }
            }

            for (int j = 0; j < 26; j++) {
                if (contador[j] == 1) letrasUnicas++;
            }

            if (letrasUnicas + perguntas == 26) {
                int proxLetra = 0;
                for (int j = i; j < i + 26; j++) {
                    if (entrada[j] == '?') {
                        while (proxLetra < 26) {
                            if (contador[proxLetra] == 0) {
                                entrada[j] = 'A' + proxLetra;
                                proxLetra++;
                                break;
                            }
                            proxLetra++;
                        }
                    }
                }
                encontrado = true;
            }
        }

        for (int i = 0; i < tamanho; i++) {
            if (entrada[i] == '?') {
                entrada[i] = 'A';
            }
        }

        if (encontrado) {
            printf("%s\n", entrada);
        } else {
            printf("-1\n");
        }
    }
    return 0;
}