Python Program to Find Longest Substring Without Repeating Characters

Finding the longest substring without repeating characters is a popular problem in coding interviews. It helps in understanding sliding window techniques and efficient string handling.

In this tutorial, we will explore multiple methods to solve this problem.

1. Understanding the Problem

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

Input: abcabcbb
Output: 3 (abc)

2. Method 1: Brute Force

              
            
Python

          Brute force approach
        
string = input()
max_len = 0

for i in range(len(string)):
    seen = set()
    for j in range(i, len(string)):
        if string[j] in seen:
            break
        seen.add(string[j])
    max_len = max(max_len, len(seen))

print(max_len)

This method checks all substrings and is not efficient for large inputs.

3. Method 2: Sliding Window (Using Set)

              
            
Python

          Sliding window with set
        
string = input()
char_set = set()
left = 0
max_len = 0

for right in range(len(string)):
    while string[right] in char_set:
        char_set.remove(string[left])
        left += 1
    char_set.add(string[right])
    max_len = max(max_len, right - left + 1)

print(max_len)

This efficient method uses a sliding window to track unique characters.

4. Method 3: Sliding Window (Using Dictionary)

              
            
Python

          Optimized sliding window
        
string = input()
char_index = {}
left = 0
max_len = 0

for right, char in enumerate(string):
    if char in char_index and char_index[char] >= left:
        left = char_index[char] + 1
    char_index[char] = right
    max_len = max(max_len, right - left + 1)

print(max_len)

This method optimizes the sliding window by jumping indices.

5. Method 4: Using Function

              
            
Python

          Reusable function
        
def longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

print(longest_substring("abcabcbb"))

Encapsulating logic in a function improves readability and reuse.

6. Method 5: Return Actual Substring

              
            
Python

          Return substring
        
string = input()
char_set = set()
left = 0
max_len = 0
result = ""

for right in range(len(string)):
    while string[right] in char_set:
        char_set.remove(string[left])
        left += 1
    char_set.add(string[right])

    if right - left + 1 > max_len:
        max_len = right - left + 1
        result = string[left:right+1]

print(result)

This method returns the actual longest substring instead of just its length.

7. Algorithm

1. Initialize two pointers (left and right).

2. Use a set or dictionary to track characters.

3. Expand window by moving right pointer.

4. Shrink window when duplicate is found.

5. Track maximum length.

6. Return result.

8. Common Mistakes

1. Not updating left pointer correctly.

2. Forgetting to remove characters from set.

3. Using inefficient brute force for large inputs.

4. Confusing substring with subsequence.

9. Applications

1. String pattern analysis.

2. Data compression techniques.

3. NLP preprocessing.

4. Interview problem solving.

Conclusion

This problem is a must-know for coding interviews and helps you master the sliding window technique.

The dictionary-based sliding window approach is the most optimized solution.