Illustration leetcode - 3. longest substring without repeated characters (difficulty: medium)

One 、 subject

Given a string  s, Please find out There are no duplicate characters Of   Longest substrings   The length of .

Two 、 Example

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" It's a Subsequence , Not substring .

Tips ：

• 0 <= s.length <= 5 * 104
• s  By the English letters 、 Numbers 、 Symbols and spaces

3、 ... and 、 Their thinking

3.1> Ideas 1： Brute force

Through two layers for Loop can realize brute force cracking to find non repeating strings , Outermost layer i loop , As the header node of each sub string generation ; The second floor j loop , Each time from i Position start , Assemble substring . Finally, select the longest as the return value . The specific logic is shown in the figure below ：

3.2> Ideas 2： The sliding window

adopt start Pointers and i The pointer , We can Construct a window , All elements in the window , There is a very important feature , Namely —— All are No repetition Of . therefore , Elements in the window , There is no need to traverse the comparison . therefore , When duplicate elements are found , We assign values directly start = index(c) -1 To achieve start The jump of . Because in the whole window , In order to start Start with i The end of the , therefore , adopt i - start You can calculate the length of the non repeating string . The specific logic is shown in the figure below ：

Four 、 Code implementation

4.1> Realization 1： Brute force

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0, temp = 0;
        Map<Character, Integer> map;
        for (int i = 0; i < s.length(); i++) {
            map = new HashMap();
            temp = 0;
            for (int j = i; j < s.length(); j++) {
                if (map.get(s.charAt(j)) != null) {
                    break;
                } else {
                    map.put(s.charAt(j), j);
                    result = Math.max(result, ++temp);
                }
            }
        }
        return result;
    }
}

4.2> Realization 2： The sliding window

class Solution {
    public int lengthOfLongestSubstring(String s) {     
        int[] mark = new int[128];// ascii code 
        int start = 0, result = 0;
        for (int i = start; i < s.length(); i++) {
            if (mark[s.charAt(i)] - 1 >= start ) { //  Duplicate values encountered ,  And the dotted subscript value is not less than start Pointer subscript 
                result = Math.max(result, i - start); //  Calculate the current length without duplicate characters 
                start = mark[s.charAt(i)]; //  Reset start The pointer                    
            }    
            mark[s.charAt(i)] = i + 1;
        }
        return Math.max(result, s.length() - start);
    }
}

That's all for today's article ：

Writing is not easy to , An article completed by the author in hours or even days , I just want to get your praise for a few seconds & Share .

More technical dry goods , Welcome everyone to follow the official account “ Java Muse ”(^o^)/~ 「 Dry cargo sharing , Weekly update 」

Previous selections

LeetCode Work: ——565. Array nesting （ difficulty ： secondary ）

LeetCode Work: ——2. Addition of two numbers （ difficulty ： secondary ）

LeetCode Work: ——735. Planetary collision （ difficulty ： secondary ）

LeetCode Work: ——1252. The number of odd cells （ difficulty ： Simple ）

Title source ： Power button （LeetCode）