[record of question brushing] 3 Longest substring without duplicate characters

One 、 Title Description

source ：

Power button （LeetCode）

Given a string  s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .

Example  1:

Input : s = "abcabcbb"

Output : 3

explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

Example  2:

Input : s = "bbbbb" Output : 1 explain :  Because the longest substring without repeating characters is  "b", So its length is  1. Example  3:

Input : s = "pwwkew"

Output : 3

explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.   Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .

Tips ：

• 0 <= s.length <= 5 * 104

• s&nbsp; By the English letters 、 Numbers 、 Symbols and spaces

Two 、 Thought analysis

Idea of window scanning

• Define a record starting start  And at the end of a record  end  For example 1  Medium  
  abc
    This window （start=0,end=3） It meets the requirements of the topic

• When the window continues to expand to  
  abca
  when , Will not be satisfied , We can only let someone move start（start+n）, Until there is no repetition , The example changes to  
  bca
  .

• Keep recording the length of the window during the window scanning （end-start）, Update to the largest during the move . It is the final answer we need

• At the same time, in order to quickly determine whether there are duplicate values and value positions in the acquisition window   We can use a hash table to record values and positions .

3、 ... and 、 Code implementation

class Solution {
 public int lengthOfLongestSubstring(String s) {
 
 HashMap<Character,Integer> map = new HashMap<>();

 // Records of the results   That is, the maximum length of the window
 int resultMax = 0;

 // The first left and right boundaries of the window
 int start = 0;
 int end = 0;
 for ( end = 0; end < s.length() ; end ++) {

 if (map.containsKey(s.charAt(end))){
 // When there are duplicate values in the window   Move the left border of the window start
 start = Math.max(start,map.get(s.charAt(end)) + 1);
 }

 map.put(s.charAt(end),end);

 resultMax = Math.max(resultMax,end - start + 1 );

 }
 return resultMax;
 }
}


Running results

Time complexity ：

summary

The meaning of this question is

Window slide

The concept and implementation steps of .

Master this idea , We can also apply it to solve other problems .