> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/stringff0c_zi_fu_chuan_lei/522string__2.md).

# Substring 结构和遍历

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

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

  ![](/files/-MUt7ZzFDAp2zELgTs5e)

  ![](/files/-MUt7ZzG3DeQ0RQEyJqU)
* **给定一个长度为 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;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/stringff0c_zi_fu_chuan_lei/522string__2.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.