La siguiente es una pregunta de demostración de un sitio de entrevistas de codificación llamado codilidad:

Un prefijo de una cadena S es cualquier parte contigua principal de S. Por ejemplo, "c" y "bacalao" son prefijos de la cadena "codilidad". Por simplicidad, requerimos que los prefijos no estén vacíos.

El producto del prefijo P de la cadena S es el número de ocurrencias de P multiplicado por la longitud de P. Más precisamente, si el prefijo P consta de K caracteres y P aparece exactamente T veces en S, entonces el producto es igual a K * T.

Por ejemplo, S = "abababa" tiene los siguientes prefijos:

"a", cuyo producto es igual a 1 * 4 = 4,"ab", cuyo producto es igual a 2 * 3 = 6,"aba", cuyo producto es igual a 3 * 3 = 9,"abab", cuyo producto es igual a 4 * 2 = 8,"ababa", cuyo producto es igual a 5 * 2 = 10,"ababab", cuyo producto es igual a 6 * 1 = 6,"abababa", cuyo producto es igual a 7 * 1 = 7.

El prefijo más largo es idéntico a la cadena original. El objetivo es elegir un prefijo que maximice el valor del producto. En el ejemplo anterior, el producto máximo es 10.

A continuación se muestra mi pobre solución en Java que requiere tiempo O (N ^ 2). Aparentemente es posible hacer esto en O (N). Estaba pensando en el algoritmo de Kadanes. Pero no puedo pensar en ninguna forma en que pueda codificar alguna información en cada paso que me permita encontrar el máximo de ejecución. ¿Alguien puede pensar en un algoritmo O (N) para esto?

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;
    }
}