Solving the interview problem Longest Substring Without Repeating Characters [+ ВИДЕО]
Formulation of the problem
Given a line s
you need to find the length of the longest substring without repeating characters.
Approach to the solution
To solve this problem, we will use the “sliding window” technique. The essence of the approach is to use two pointers that will represent the current substring, and a set to track unique characters. If we encounter a repeated character, we move the left pointer to the right until we remove the repeated character from the set.
Algorithm
Let's initialize the variables:
res
to store the maximum length of a substring,left
to start the window andseen
for unique characters.We go through the line using the right pointer:
If the symbol under the right pointer is already in
seen
move the left pointer to the right, deleting characters fromseen
until we remove the repeating symbol.Add the current character under the right pointer to
seen
.We are updating
res
if the current window length is greater than the current maximum.
We return the result.
Solution code
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
left = 0
seen = set()
for right in range(len(s)):
right_char = s[right]
while right_char in seen:
left_char = s[left]
seen.remove(left_char)
left += 1
seen.add(right_char)
res = max(res, right - left + 1)
return res
Code Explanation
Initialization of variables:
res
stores the maximum length of a substring without repeating characters.left
indicates the beginning of the current window.seen
stores unique characters of the current window.
Iterate over a string:
Detecting duplicate characters:
Inside the loop
while
check if the current symbol is in the setseen
. If yes, then remove the symbol under the left pointer from the set and move the left pointer to the right.
Adding a unique symbol:
Updating the result:
Returning the result:
Visualization of the solution
Let's consider the line s = "pwwkew"
and visualize the steps of solving the problem, showing the current state of the sliding window.
Execution steps:
Iteration 0:
Current symbol: p
Window: [p]wwkew
seen: set()
Window length: 1
Window after updating the result: [p]wwkew
Current maximum: 1
Iteration 1:
Current symbol: w
Window: [pw]wkew
seen: {'p'}
Window length: 2
Window after updating the result: [pw]wkew
Current maximum: 2
Iteration 2:
Current symbol: w
Window: [pww]kew
seen: {'w', 'p'}
Window length: 3
Window reduction:
Window reduction:
Window after updating the result: pw[w]kew
Current maximum: 2
Iteration 3:
Current symbol: k
Window: pw[wk]ew
seen: {'w'}
Window length: 2
Window after updating the result: pw[wk]ew
Current maximum: 2
Iteration 4:
Current symbol: e
Window: pw[wke]w
seen: {'w', 'k'}
Window length: 3
Window after updating the result: pw[wke]w
Current maximum: 3
Iteration 5:
Current symbol: w
Window: pw[wkew]
seen: {'w', 'k', 'e'}
Window length: 4
Window reduction:
Window after updating the result: pww[kew]
Current maximum: 3
Asymptotic complexity
Time complexity: O(n). Each character of the string is added and removed from the set at most once.
Difficulty by memory: O(min(n, m)), where n is the length of the string, m is the size of the alphabet.
This algorithm is an efficient solution to the problem using the sliding window technique, which allows processing the string in linear time and preserving the unique characters of the substring.