LeetCode Question 3: The longest substring without duplicate characters

LeetCode Question 3: The longest substring without duplicate characters

Question description

Given a string s , please find out the length of the longest substring that does not contain duplicate characters.

Difficulty

medium

Title link

/problems/longest-substring-without-repeating-characters/

Example

Example 1:

Enter: s = "abcabcbb"
 Output: 3
 Explanation: Because the longest substring without duplicate characters is "abc", its length is 3.

Example 2:

Enter: s = "bbbbbb"
 Output: 1
 Explanation: Because the longest substring without duplicate characters is "b", its length is 1.

Example 3:

Enter: s = "pwwkew"
 Output: 3
 Explanation: Because the longest substring without duplicate characters is "wke", its length is 3.
      Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.

hint

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

Problem-solving ideas

Method 1: Sliding the window

This problem can be solved using the sliding window method. A sliding window is a technique of using double pointers on an array or string. By moving the left and right pointers to form a window, it operates within the window.

Key points:

1. Maintain a sliding window using two pointers (left and right)
2. Use HashSet to record characters in the window to ensure no duplication
3. When a duplicate character is encountered, move the left pointer until the duplicate character is deleted
4. Update the maximum length during movement

Specific steps:

1. Initialize left pointer left = 0, right pointer right = 0
2. Create characters in the HashSet storage window
3. Move the right pointer and add the character to Set:
   • If the character is not in the Set, add the Set and update the maximum length
   • If the character is in Set, move the left pointer and delete the character until there is no duplication
4. Repeat step 3 until the right pointer reaches the end of the string

Time complexity: O(n), where n is the string length
Space complexity: O(min(m,n)), where m is the character set size

Method 2: Optimized sliding window

Use Dictionary/HashMap instead of HashSet to store the last position of the character. You can directly jump to the left pointer position to avoid deleting characters one by one.

Code implementation

C# implementation (basic sliding window)

public class Solution {
     public int LengthOfLongestSubstring(string s) {
         // Special circumstances handling
         if ((s)) return 0;
      
         // Create a HashSet to store characters in the current window
         HashSet<char> window = new HashSet<char>();
         int maxLength = 0;
         int left = 0;
      
         // Right pointer traversing string
         for (int right = 0; right < ; right++) {
             // If duplicate characters are found，Move the left pointer until duplicate characters are deleted
             while ((s[right])) {
                 (s[left]);
                 left++;
             }
          
             // Add the current character to the window
             (s[right]);
          
             // Update the maximum length
             maxLength = (maxLength, right - left + 1);
         }
      
         return maxLength;
     }
 }

C# implementation (optimized sliding window)

public class Solution {
     public int LengthOfLongestSubstring(string s) {
         // Special circumstances handling
         if ((s)) return 0;
      
         // Create the Dictionary store where the last character appears
         Dictionary<char, int> lastPos = new Dictionary<char, int>();
         int maxLength = 0;
         int left = 0;
      
         // Right pointer traverses the string
         for (int right = 0; right < ; right++) {
             char currentChar = s[right];
          
             // If the character already exists, move the left pointer directly to the next bit of the repeated character
             if ((currentChar)) {
                 left = (left, lastPos[currentChar] + 1);
             }
          
             // Update the last character to appear
             lastPos[currentChar] = right;
          
             // Update the maximum length
             maxLength = (maxLength, right - left + 1);
         }
      
         return maxLength;
     }
 }

Detailed code explanation

Basic sliding window version:

1. HashSet<char> window: Used to store characters in the current window, ensuring no duplication
2. while ((s[right])): When repeated characters are found, constantly move the left pointer and delete the characters
3. maxLength = (maxLength, right - left + 1): Update the maximum length

Optimized version:

1. Dictionary<char, int> lastPos: Store the last location of each character
2. left = (left, lastPos[currentChar] + 1)：
   • When a duplicate character is found, move the left pointer directly to the next position where the duplicate character last appeared
   • Used to prevent the left pointer from falling back

Execution results

Basic sliding window version:

• Execution time: 84 ms
• Memory consumption: 39.5 MB

Optimized version:

• Execution time: 72 ms
• Memory consumption: 39.8 MB

Summary and reflection

1. This is a classic sliding window topic that examines:
   • Basic application of sliding window
   • Processing of strings
   • Use of hash tables
2. The two implementation methods have their own advantages:
   • The basic version is more intuitive and easy to understand
   • Optimized version performance is better, avoiding multiple moves of left pointer
3. Key points:
   • Understand the difference between substrings and subsequences
   • Properly maintain the sliding window
   • Efficiently handle duplicate characters

Related topics

• LeetCode Question 159: The longest substring containing at most two different characters
• LeetCode Question 340: The longest substring containing at most K different characters
• LeetCode Question 395: The longest substring with at least K repeating characters
• LeetCode Question 424: The longest repeated character after replacement