Longest Substring Without Repeating Characters Python Program

Longest Substring Without Repeating Characters Find the length of the longest substring without repeating characters Python Program?

To find the length of the longest substring without repeating characters, you can use the sliding window technique combined with a set to keep track of characters in the current window. This method ensures that you efficiently find the longest substring with unique characters in linear time.

Approach

1. Sliding Window: Use two pointers to represent the current window of characters. The left pointer represents the start of the window, and the right pointer represents the end of the window.

2. Hash Set: Use a set to keep track of characters in the current window. This allows for $O(1)$ time complexity for insertions and deletions.

3. Expand and Contract the Window: Expand the window by moving the right pointer and add characters to the set. If a duplicate character is found, contract the window by moving the left pointer until the duplicate character is removed.

4. Track the Maximum Length: Keep track of the maximum length of substrings encountered during the process.

Python Implementation

Here's a Python program to achieve this:

def length_of_longest_substring(s):

    char_set = set()  # To store characters in the current window

    left = 0  # Left pointer of the window

    max_length = 0  # Maximum length of substring found

    for right in range(len(s)):

        # If the character is already in the set, remove characters from the left until it's not

        while s[right] in char_set:

            char_set.remove(s[left])

            left += 1

        

        # Add the current character to the set

        char_set.add(s[right])

        

        # Update the maximum length found

        max_length = max(max_length, right - left + 1)

    

    return max_length

# Example usage:

s = "abcabcbb"

print(length_of_longest_substring(s))  # Output: 3

Explanation

1. Initialization:

   • char_set is a set to track unique characters in the current window.
   • left is the starting index of the sliding window.
   • max_length keeps track of the longest substring found.

2. Iterate through the String:

   • For each character at the right pointer, check if it is in the char_set.
   • If it is, remove characters from the char_set starting from the left pointer until the duplicate character is removed.
   • Add the current character to the char_set and update the maximum length of the substring.

3. Update Length:

   • Calculate the length of the current window (right - left + 1) and update max_length if the current window is larger.

Complexity

• Time Complexity: $O(n)$, where $n$ is the length of the string. Each character is processed at most twice (once when expanding and once when contracting the window).
• Space Complexity: $O(min(n, m))$, where $m$ is the size of the character set. For example, in ASCII, $m$ is 128, and in Unicode, it can be much larger, but it's still limited by the character set used.

This approach efficiently finds the length of the longest substring without repeating characters using a sliding window and set-based tracking.