leetcode 3. Longest Substring Without Repeating Characters 无重复字符的最长子串(leetcode 3. Longest substring without repeating characters)

一、题目大意

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

给定一个字符串 s ,请你找出其中不含有重复字符的 **最长子串 **的长度。
示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。

提示:

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

二、解题思路

滑动窗口的思路解决

三、解题方法

3.1 Java实现

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] chars = new int[128];
        int left = 0;
        int maxSize = 0;
        // 窗口右边界向右滑
        for (int right = 0; right < s.length(); right++) {
            chars[s.charAt(right)]++;
            if (chars[s.charAt(right)] == 1) {
                maxSize = Math.max(right - left + 1, maxSize);
            } else {
                // 窗口左边界向右滑
                while(chars[s.charAt(right)] != 1) {
                    chars[s.charAt(left)]--;
                    left++;
                }
            }
        }
        return maxSize;
    }
}

四、总结小记

  • 2022/5/15 滑动窗口,重点是:窗口在滑动的过程中记录什么值最终要求什么值,以及窗口左边界向右滑的结束条件是什么
————————

1、 General idea of the topic

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

Given a string s, please find out the length of * * longest substring * * which does not contain duplicate characters.
< strong > example 1: < / strong >

Enter: S = “abcabcbb”
Output: 3
Explanation: because the longest substring without repeated characters is “ABC”, its length is 3.

Enter: S = “abcabcbb”
Output: 3
Explanation: because the longest substring without repeated characters is “ABC”, its length is 3.

< strong > example 2: < / strong >

Input: S = “bbbbb”
Output: 1
Explanation: because the longest substring without repeated characters is “B”, its length is 1.

Input: S = “bbbbb”
Output: 1
Explanation: because the longest substring without repeated characters is “B”, its length is 1.

< strong > example 3: < / strong >

Input: S = “pwwkew”
Output: 3
Explanation: because the longest substring without repeated characters is “WKE”, its length is 3.
Please note that your answer must be the length of the substring, “pwke” is a substring, not a substring.

Input: S = “pwwkew”
Output: 3
Explanation: because the longest substring without repeated characters is “WKE”, its length is 3.
Please note that your answer must be the length of the substring, “pwke” is a substring, not a substring.

< strong > prompt: < / strong >

  • 0 <= s.length <= 5 * 104
  • S , consists of English letters, numbers, symbols and spaces

2、 Problem solving ideas

Solution of sliding window

3、 Problem solving method

3.1 Java实现

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] chars = new int[128];
        int left = 0;
        int maxSize = 0;
        // 窗口右边界向右滑
        for (int right = 0; right < s.length(); right++) {
            chars[s.charAt(right)]++;
            if (chars[s.charAt(right)] == 1) {
                maxSize = Math.max(right - left + 1, maxSize);
            } else {
                // 窗口左边界向右滑
                while(chars[s.charAt(right)] != 1) {
                    chars[s.charAt(left)]--;
                    left++;
                }
            }
        }
        return maxSize;
    }
}

4、 Summary notes

  • 2022 / 5 / 15 sliding window, focusing on: what value is recorded in the sliding process of the window, what value is finally required, and what is the end condition of sliding the left boundary of the window to the right