title: Maximum product prefix string
body: <p>The following is a demo question from a coding interview site called codility:</p>
  
  <blockquote>
    <p>A prefix of a string S is any leading contiguous part of S. For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty.</p>
    
    <p>The product of prefix P of string S is the number of occurrences of P multiplied by the length of P. More precisely, if prefix P consists of K characters and P occurs exactly T times in S, then the product equals K * T.</p>
    
    <p>For example, S = "abababa" has the following prefixes:</p>
    
    <ul>
    <li>"a", whose product equals 1 * 4 = 4,</li>
    <li>"ab", whose product equals 2 * 3 = 6,</li>
    <li>"aba", whose product equals 3 * 3 = 9,</li>
    <li>"abab", whose product equals 4 * 2 = 8,</li>
    <li>"ababa", whose product equals 5 * 2 = 10,</li>
    <li>"ababab", whose product equals 6 * 1 = 6,</li>
    <li>"abababa", whose product equals 7 * 1 = 7.</li>
    </ul>
    
    <p>The longest prefix is identical to the original string. The goal is to choose such a prefix as maximizes the value of the product. In above example the maximal product is 10.</p>
  </blockquote>
  
  <p>Below is my poor solution in Java requiring O(N^2) time. It is apparently possible to do this in O(N). I was thinking Kadanes algorithm. But I can't think of any way that I can encode some information at each step that lets me find the running max. Can any one think of an O(N) algorithm for this?</p>
  
  <pre class="lang-java prettyprint-override"><code>import java.util.HashMap;
  
  class Solution {
      public int solution(String S) {
          int N = S.length();
          if(N&lt;1 || N&gt;300000){
              System.out.println("Invalid length");
              return(-1);
          }
          HashMap&lt;String,Integer&gt; prefixes = new HashMap&lt;String,Integer&gt;();
          for(int i=0; i&lt;N; i++){
              String keystr = "";
              for(int j=i; j&gt;=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 &gt; 1000000000)return 1000000000;
                      prefixes.put(keystr,newval);
                  }
              }
          }
          int maax1 = 0;
          for(int val : prefixes.values())
              if(val&gt;maax1)
                  maax1 = val;
          return maax1;
      }
  }
  </code></pre>