Solving the interview problem Longest Substring Without Repeating Characters [+ ВИДЕО]

Formulation of the problem

Given a line syou 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

1. Let's initialize the variables: res to store the maximum length of a substring, left to start the window and seen for unique characters.

2. We go through the line using the right pointer:

   • If the symbol under the right pointer is already in seenmove the left pointer to the right, deleting characters from seenuntil we remove the repeating symbol.

   • Add the current character under the right pointer to seen.

   • We are updating resif the current window length is greater than the current maximum.

3. 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

1. 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.

2. Iterate over a string:

3. Detecting duplicate characters:

   • Inside the loop while check if the current symbol is in the set seen. If yes, then remove the symbol under the left pointer from the set and move the left pointer to the right.

4. Adding a unique symbol:

5. Updating the result:

6. 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.