Longest Substring Without Repeating Characters in Python

The term "longest substring without repeating characters" refers to finding the longest sequence of characters in a string where no character is repeated. For example, in the string "abcabcbb", the longest substring without repeating characters is "abc", which has a length of 3.

This problem is commonly encountered in fields like data analysis, text processing, and software development. For instance, when developing a text editor, you might want to highlight the longest segment of text that doesn't repeat any characters. It can also help in optimizing algorithms that require unique sequences, such as password validation systems to ensure stronger security by avoiding repeated characters in passwords.

Problem statement

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

Sample input

1s = "abcabcbb"

Sample output

1output = 3

Idea to solve

To solve this problem, we can use a sliding window approach with two pointers to keep track of the current substring without repeating characters. We also use a set to store the characters in the current window. As we move through the string, we adjust the window to ensure that no characters are repeated.

Pseudo code

Here’s the pseudo code for solving the problem:

• Initialize a set to store characters in the current window.
• Use two pointers, left and right, both starting at the beginning of the string.
• Initialize max_length to keep track of the maximum length of the substring found.
• While right is less than the length of the string:
  • If the character at right is not in the set:
    • Add the character to the set.
    • Update max_length if the current window size is larger.
    • Move right one step to the right.
  • If the character at right is in the set:
    • Remove the character at left from the set.
    • Move left one step to the right.
• Return max_length.

Full code

Here's the complete Python code to find the longest substring without repeating characters:

1def longest_substring_without_repeating_characters(s):
2    char_set = set()
3    left = 0
4    max_length = 0
5    
6    for right in range(len(s)):
7        while s[right] in char_set:
8            char_set.remove(s[left])
9            left += 1
10        char_set.add(s[right])
11        max_length = max(max_length, right - left + 1)
12    
13    return max_length
14
15# Sample input
16s = "abcabcbb"
17# Calling the function and printing the result
18output = longest_substring_without_repeating_characters(s)
19print("Length of the longest substring without repeating characters:", output)

Explanation of the code

Initialization: We initialize a set char_set to store characters in the current window, left pointer to the start of the window, and max_length to track the maximum length of the substring found.

Sliding Window: We use a for loop to iterate through the string with the right pointer.

Checking for Repeats: Inside the loop, we use a while loop to check if the character at the right pointer is already in the set. If it is, we remove the character at the left pointer from the set and move the left pointer to the right.

Updating the Set and Length: If the character at the right pointer is not in the set, we add it to the set and update max_length if the current window size is larger.

Return the Result: After the loop, we return max_length, which is the length of the longest substring without repeating characters.

Time complexity

The time complexity of this approach is O(n), where n is the length of the string. This is because each character is processed at most twice (once by the right pointer and once by the left pointer). The space complexity is O(min(m,n)), where mmm is the character set size and n is the length of the string, due to the storage in the set.