[Leetcode] Longest Substring Without Repeating Characters

A classic example of sliding window.

Description

Given a string s, find the length of the longest substring without repeating characters.

Examples

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

Sliding window is also named as catepillar approach. The two pointers move just like a catepillar. The right pointer(j), assembling front feet, first forwards until some contraint is violated. Then, the left pointer(i), assembling back feet and static before, forwards until the constraint is fulfilled. The relative move of two pointers is similar with how catepillar moves.

The template is quite like a pattern.

For this problem, the information of i&j is the counter that records the occurring times of chars. Move front pointer to make distance between front and back as long as possible. Update the distance into global recording variable whenver distance increases. The constraint is violated when the count of any char > 1. When this happens, shrink the distance via moving back pointer. Note that the update of i information (here it means the count of char at position i) occurs before incrementing i, otherwise the information is wronly modified. The distance between front and back will repeat the process of enlarging and shrinking. The max distance is recorded along the way.

• code

ref: https://blog.csdn.net/fuxuemingzhu/article/details/82022530