寻找字符串中不重复最长子串

问题

给定一个字符串，找出这个字符串中最长的不重复子串。假定字符串编码范围在256之内(排除中文等特殊字符)，同时如果有相同长度的子串，优先获取首次寻找的子串，时间复杂度O(N)。

• “abcd” -> “abcd”
• “abccd” -> “abc”
• “somok39ebab3yuvwz123” -> “ab3yuvwz12”

思路

• 用一个int数组position保存每个字符在字符串中的位置
• 用一个int变量mark标记下一次可获取子串的开始位置
• 用一个String变量maxUniqueStr保存循环过程中始终最长的无重复子串。

• 初始化position中每个元素值为-1，同时将字符串转化成字符数组chars
• 遍历chars数组，当前字符上次出现，取出上次的位置lastPos(注意mark必须小于lastPos)
• 获取子串, mark到当前遍历的序号i之间的子串，子串大于maxUniqueStr，则将子串保存到maxUniqueStr
• mark向前推进为当前字符的上次出现位置加1，即lastPos + 1
• 处理循环之外的最后尾部子串逻辑

代码实现

public class GetMaxUniqueSubString {


    public static String getMaxUniqueString(String str) {
        if (str == null || str.length() == 0 ) {
            return "";
        }
        //循环过程中保存的最长字符串
        String maxUniqueStr = "";
        //标记位
        int mark = 0;
        char[] chars = str.toCharArray();
        //存放字符的位置
        int[] position = new int[256];
        //位置都初始化-1,表示未发现
        for (int i=0;i<position.length;i++) {
            position[i] = -1;
        }
        for (int i=0;i<chars.length;i++) {
            //当前字符的上一次出现位置
            int lastPos = position[chars[i]];
            //不为-1表示之前出现过该字符
            if (lastPos != -1 && mark <= lastPos) {
                String subStr = str.substring(mark, i);
                if (subStr.length() > maxUniqueStr.length()) {
                    maxUniqueStr = subStr;
                }
                mark = lastPos + 1;
            }
            position[chars[i]] = i;
        }
        //可能漏掉结尾一段
        if (mark <= chars.length) {
            String subStr = str.substring(mark, chars.length);
            if (subStr.length() > maxUniqueStr.length()) {
                maxUniqueStr = subStr;
            }
        }

        return maxUniqueStr;
    }

    public static void main(String[] args) {
        String str = "abccd";
        String maxUniqueString = getMaxUniqueString(str);
        System.out.println(maxUniqueString);
    }
}