重复出现次数最多的子串中最长的子串

面试题

找重复出现次数最多的子串中最长的那个子串。例：
“abcdabc” 2次abc
“bbbb” 4次b

思路：
记录每个长度的字串重复出现的次数，然后找到出现次数最多的所有字串，返回最长的那个。

如，abcdabc，长度为1的字串有a:2,b:2,c:2,d:1，长度为2的字串有ab:2,bc:2,ca:1，长度为3的字串有abc:2,bcd:1,cda:1,dab:1，长度为4的有abcd:1,bcda:1,dabc:1，长度为5的有abcda:1,bcdab:1,cdabc:1，长度为6的有abcdab:1,bcdabc:1，长度为7的有abcdabc:1。其中出现最多的是2次，有a:2,b:2,c:2, ab:2,bc:2, abc:2。其中长度最长的是abc。

因此可以这样写：

package com.youthlin;

import java.util.*;

/**
 * Created by lin on 2016-04-20-020.
 * 面试题
 * 重复出现次数最多的子串中最长的那个子串
 * "abcabc" 2次abc
 * "bbbb" 4次b
 */
public class LongestMaxCountString {
    public static String getLongestMaxCountString(String s) {
        String result;
        Map<String, Integer> map = new HashMap<>();//<子串，出现次数>
        for (int i = 1; i <= s.length(); i++) {
            //检查长度为i个字符的子串重复出现的次数
            for (int j = 0; j < s.length(); j++) {
                if (i + j <= s.length()) {
                    result = s.substring(j, j + i);
                    if (map.containsKey(result))
                        map.put(result, map.get(result) + 1);
                    else map.put(result, 1);
                }
            }
        }
        int count;
        result = null;
        Map<Integer, String> map1 = new HashMap<>();//<次数，最长子串>
        Set<String> keys = map.keySet();
        for (String key : keys) {
            count = map.get(key);
            if (map1.containsKey(count)) {
                result = map1.get(count);
                if (key.length() > result.length())//看新的子串长度是否更大
                    map1.put(count, key);
            } else
                map1.put(count, key);
        }
        count = 0;
        Set<Integer> set = map1.keySet();
        for (Integer a : set) {//找出次数最多的子串
            if (a > count) {
                count = a;
                result = map1.get(a);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "abcdabcdeabcd";
        System.out.println(getLongestMaxCountString(s));
        s = "bbbb";
        System.out.println(getLongestMaxCountString(s));
        s = "";
        System.out.println(getLongestMaxCountString(s));
    }
    /**输出：
     * abcd
     * b
     * null
     */
}

听说是Leecode上的题目，我搜到了一些用后缀数组解法的，但并没有看明白，上面这种方法也是最笨的方法，不知道还有什么复杂度更低的方法。