LeetCode 3. Longest Substring Without Repeating Characters

Post by ailswan Mar. 08, 2024

3. Longest Substring Without Repeating Characters

Problem Statement

link: LeetCode.cn LeetCode

Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb" Output: 3

Input: s = "bbbbb" Output: 1

Input: s = "pwwkew" Output: 3

Solution Approach

The algorithm efficiently utilizes a sliding window technique to find the longest substring without repeating characters, maintaining the window boundaries and updating the maximum length accordingly.

Algorithm

  1. The algorithm initializes a dictionary to store the most recent index of each character encountered.
  2. It defines a sliding window represented by two pointers, ‘left’ and ‘right’, to iterate over the string.
  3. As the window expands, it updates the maximum length of the substring without repeating characters and adjusts the ‘left’ pointer when a repeating character is encountered, ensuring no repeating characters are within the window.

Implement

    class Solution:
      def lengthOfLongestSubstring(self, s: str) -> int:
          visited = {}
          left = 0
          res = 0
          for i, c in enumerate(s):
              if c in visited and left <= visited[c]:
                  left = visited[c] + 1
              else:
                  res = max(res, i - left + 1)
              visited[c] = i
          return res