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

General
1

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

2

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

Answer: To solve the problem of finding the length of the longest substring without repeating characters in a string ( s ), you can use the sliding window technique along with a hash set to keep track of characters. Here’s a step-by-step explanation and the Python code to achieve this:

Step-by-Step Explanation

  1. Initialize Variables:

    • start: This will be the starting index of our sliding window.
    • max_length: This will store the length of the longest substring found without repeating characters.
    • char_set: A set to store characters in the current window.

  2. Iterate Through the String:

    • Use a for loop to iterate through the string with an index end representing the end of the current window.
    • If the character at s[end] is not in char_set, add it to the set.
    • Update max_length to be the maximum of its current value and the size of the current window (end - start + 1).

  3. Adjust the Window:

    • If the character at s[end] is already in char_set, this means we have encountered a repeating character.
    • Remove characters from the start of the window (s[start]) until we remove the repeating character.
    • Increment start to shrink the window from the left.

  4. Return the Result:

    • After iterating through the string, max_length will contain the length of the longest substring without repeating characters.

Python Code

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    start = 0
    max_length = 0

    for end in range(len(s)):
        while s[end] in char_set:
            char_set.remove(s[start])
            start += 1
        char_set.add(s[end])
        max_length = max(max_length, end - start + 1)

    return max_length

# Example usage
s = "abcabcbb"
print(length_of_longest_substring(s))  # Output: 3

Explanation with Example

Let’s take the example string s = "abcabcbb":

  1. Initial State:

    • start = 0
    • max_length = 0
    • char_set = {}

  2. Iteration 1 (end = 0):

    • s[end] = 'a'
    • char_set = {'a'}
    • max_length = max(0, 0 - 0 + 1) = 1

  3. Iteration 2 (end = 1):

    • s[end] = 'b'
    • char_set = {'a', 'b'}
    • max_length = max(1, 1 - 0 + 1) = 2

  4. Iteration 3 (end = 2):

    • s[end] = 'c'
    • char_set = {'a', 'b', 'c'}
    • max_length = max(2, 2 - 0 + 1) = 3

  5. Iteration 4 (end = 3):

    • s[end] = 'a' (repeating character)
    • Remove characters from start until s[end] is not in char_set
      • Remove s[start] = 'a', increment start to 1
    • char_set = {'b', 'c'}
    • Add s[end] = 'a' to char_set
    • max_length remains 3

Continue this process for the entire string. The final value of max_length will be 3, which is the length of the longest substring without repeating characters (“abc”).

This approach ensures that each character is processed at most twice (once when added and once when removed), resulting in an efficient ( O(n) ) time complexity.