Given a string s, find the length of the longest substring without duplicate characters. 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. Constraints: 0 <= s.length <= 5 * 104 s consists of English letters, digits, symbols and spaces. Seen this question in a real interview before? 1/5 Yes No Accepted 7,819,834/21M Acceptance Rate 37.2% explain me this problem in the video form

视频信息

答案文本 复制

视频字幕 复制

Today we'll solve the longest substring without duplicate characters problem. Given a string, we need to find the length of the longest substring where all characters are unique. It's important to understand that we need a substring, which means consecutive characters, not a subsequence where characters can be in any order. For example, in the string 'pwwkew', the longest substring without duplicates is 'wke' with length 3, while 'pwke' would be a subsequence but not a valid substring. The brute force approach checks all possible substrings. We use two nested loops: the outer loop sets the starting position i, and the inner loop extends the ending position j. For each substring from i to j, we check if it contains duplicate characters using a hash set. This gives us O(n³) time complexity because we have O(n²) possible substrings and each duplicate check takes O(n) time. While this works, it's inefficient for large strings. The sliding window technique uses two pointers to maintain a window of unique characters. We expand the right pointer to grow the window and contract the left pointer when we encounter duplicates. This approach visits each character at most twice, giving us O(n) time complexity. Let's see how it works with the example 'abca'. We start with both pointers at position 0, then expand the window until we find a duplicate, at which point we contract from the left. Today we'll solve the problem of finding the longest substring without repeating characters. Given a string, we need to find the maximum length of any substring that contains no duplicate characters. For example, in 'abcabcbb', the answer is 'abc' with length 3. Let's explore different approaches to solve this efficiently. The brute force approach checks every possible substring. We start from each position and extend until we find a duplicate character. This requires three nested loops: one for the start position, one for the end position, and one to check for duplicates. The time complexity is O(n³) which is inefficient for large inputs. The sliding window technique is much more efficient. We use two pointers to maintain a window of unique characters. We expand the right pointer to grow the window, and when we encounter a duplicate, we contract the left pointer. This gives us O(n) time complexity instead of O(n³). Here's the complete sliding window implementation. We use a hash map to store character positions and two pointers for the window boundaries. For each character, if it's already in our map and within the current window, we move the left pointer. We then update the character's position and track the maximum window size. Let's trace through 'pwwkew' step by step to see how the algorithm handles duplicate characters and maintains the optimal window. Let's summarize our solution. The sliding window approach achieves O(n) time complexity because each character is visited at most twice - once by the right pointer and once by the left pointer. The space complexity is O(min(m,n)) where m is the character set size. The key insights are: sliding window avoids redundant work, hash map enables constant-time duplicate detection, and two pointers maintain the optimal window efficiently. This sliding window technique is a powerful pattern that applies to many similar substring and subarray problems in competitive programming and interviews. Let's analyze the complexity of our solution. The sliding window approach achieves O(n) time complexity because each character is visited at most twice - once by the right pointer expanding the window, and once by the left pointer contracting it. The space complexity is O(min(m,n)) where m is the character set size. Compared to the brute force O(n³) approach, this is dramatically more efficient. We also need to handle edge cases: empty strings return 0, single characters return 1, strings with all duplicates return 1, and strings with all unique characters return the string length.