# Substring 结构和遍历

## [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

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

  ![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2F0563dbb09cdb21b24988187048681c61076e8709.PNG?generation=1614792525237075\&alt=media)

  ![](https://2030049235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MUt7Y8-dUQcwNZkL6dz%2Fsync%2F6ae015d86f97601632965e5a934b3fa5c321ba09.PNG?generation=1614792525063082\&alt=media)
* **给定一个长度为 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 问题。**
* **这题我后面在双指针的地方重写了，比这个简单。**

```java
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;
    }
}
```

* **双指针重写版:**

```java
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;
    }
}
```