分类
代码

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

面试题

找重复出现次数最多的子串中最长的那个子串。例:
“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上的题目,我搜到了一些用后缀数组解法的,但并没有看明白,上面这种方法也是最笨的方法,不知道还有什么复杂度更低的方法。


“重复出现次数最多的子串中最长的子串”上的5条回复

沙发!
常规思路,但效率较差。
这种在网站里一般用在自动提取标签上,找到文本中出现频率最高的5个字符串,提取作为标签。
目前绝大多网站用的都是标签字典,类似于搜索引擎那种,所以效率很高。
至于不依赖外部字典自动提取……我记得有什么方法,但忘了……

又仔细看了下,貌似这题出的有些奇怪,和标签提取还不是一回事……
“找重复出现次数最多的子串中最长的那个子串”,首先是“出现次数最多”,其次才是“最长的字符串”。
那例如“abcdabca”这段中肯定是“a”出现次数最多,这么看来貌似你那答案蛮不错的……

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

[/鼓掌] [/难过] [/调皮] [/白眼] [/疑问] [/流泪] [/流汗] [/撇嘴] [/抠鼻] [/惊讶] [/微笑] [/得意] [/大兵] [/坏笑] [/呲牙] [/吓到] [/可爱] [/发怒] [/发呆] [/偷笑] [/亲亲]