A seguir, uma pergunta demo de um site de entrevista de codificação chamado codility:

Um prefixo de uma string S é qualquer parte contígua inicial de S. Por exemplo, "c" e "cod" são prefixos da string "codility". Para simplificar, exigimos que os prefixos não estejam vazios.

O produto do prefixo P da string S é o número de ocorrências de P multiplicado pelo comprimento de P. Mais precisamente, se o prefixo P consistir em K caracteres e P ocorrer exatamente T vezes em S, o produto será igual a K * T.

Por exemplo, S = "abababa" possui os seguintes prefixos:

"a", cujo produto é igual a 1 * 4 = 4,"ab", cujo produto é igual a 2 * 3 = 6,"aba", cujo produto é igual a 3 * 3 = 9,"abab", cujo produto é igual a 4 * 2 = 8,"ababa", cujo produto é igual a 5 * 2 = 10,"ababab", cujo produto é igual a 6 * 1 = 6,"abababa", cujo produto é igual a 7 * 1 = 7.

O prefixo mais longo é idêntico à sequência original. O objetivo é escolher um prefixo que maximize o valor do produto. No exemplo acima, o produto máximo é 10.

Abaixo está minha solução ruim em Java, exigindo tempo O (N ^ 2). Aparentemente, é possível fazer isso em O (N). Eu estava pensando no algoritmo Kadanes. Mas não consigo pensar em nenhuma maneira de codificar algumas informações a cada etapa que me permitam encontrar o máximo em execução. Alguém pode pensar em um algoritmo O (N) para isso?

import java.util.HashMap;

class Solution {
    public int solution(String S) {
        int N = S.length();
        if(N<1 || N>300000){
            System.out.println("Invalid length");
            return(-1);
        }
        HashMap<String,Integer> prefixes = new HashMap<String,Integer>();
        for(int i=0; i<N; i++){
            String keystr = "";
            for(int j=i; j>=0; j--) {
                keystr += S.charAt(j);
                if(!prefixes.containsKey(keystr))
                    prefixes.put(keystr,keystr.length());
                else{
                    int newval = prefixes.get(keystr)+keystr.length();
                    if(newval > 1000000000)return 1000000000;
                    prefixes.put(keystr,newval);
                }
            }
        }
        int maax1 = 0;
        for(int val : prefixes.values())
            if(val>maax1)
                maax1 = val;
        return maax1;
    }
}