Substring 结构和遍历

Longest Substring Without Repeating Characters

• Substring 类问题和 CLRS 的 Rod-Cutting 有非常紧密的联系。

  

  

• 给定一个长度为 n 的 String，它所有的 substring 数量是 n(n + 1) / 2 ，是一个 quadratic 的数量级。所以有些问题如果暴力遍历的话复杂度是没法让人满意的，某些问题如果用二维 DP 也至少需要 O(n^2) 的时间与空间开销。

• 给定一个长度为 n 的 String，切成若干个 pieces 总共有 $2^{n-1}$ 种切法，即对于所有 $n-1$ 个分界点上，选择“切/不切”.

• 此类问题最常用的优化，就是利用子串性质， abuse 子串的结构。

• 同时维护一个类似 sliding window 的结构去向尾部移动，如果是 KMP pattern matching，不回滚的 window / pattern 就可以达到 linear time.

在这个问题里，substring 里面一定没有重复字符，因此可以开一个 boolean array 作为 hash 记录 window 里面已经存在的字符。

同时如果在看到一个新字符之后出现重复的话，以这个字符为结尾的最长 substring 一定在 sliding window 里面同一个字符之后。

• “必须以当前字符结尾” 是字符串问题中很常见的 optimal substructure, 因此这个问题也类似于 DP 问题。

• 这题我后面在双指针的地方重写了，比这个简单。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1) return s.length();
        int start = 0;
        int end = 0;
        int max = 1;
        boolean[] hash = new boolean[256];
        while(end < s.length()){
            int key = (int) s.charAt(end);
            if(!hash[key]){
                hash[key] = true;
                end ++;
                max = Math.max(max, end - start);
            } else {
                while(start < end && s.charAt(start) != s.charAt(end)){
                    hash[(int)s.charAt(start)] = false;
                    start ++;
                }
                start ++;
                end ++;
            }
        }

        return max;
    }
}

• 双指针重写版:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1) return s.length();
        int max = 1;
        boolean[] hash = new boolean[256];
        int j = 0;
        for(int i = 0; i < s.length(); i++){
            while(j < s.length()){
                if(!hash[s.charAt(j)]){
                    hash[s.charAt(j++)] = true;
                } else {
                    break;
                }
            }
            max = Math.max(max, j - i);
            hash[s.charAt(i)] = false;
        }

        return max;
    }
}