The problem of finding the longest substring without repeating characters is a classic one in algorithm design. It is particularly useful for understanding the sliding window technique, which is highly efficient for solving such problems involving contiguous subarrays or substrings.

Sliding Window Approach

In this solution, we use two pointers, start and end, to maintain a sliding window that keeps track of the current substring under consideration. The idea is to expand this window as long as the characters in the substring are unique, and to contract it when a repeated character is encountered.

Steps:

  1. Initialize two pointers: start = 0, end = 0.
  2. Create a count array of size 256 to store the frequency of each character. This array will allow us to quickly determine if a character is repeating within the current window.
  3. Expand the window by increasing the end pointer. For each new character added to the window, check if it is unique. If it is, update the max_len with the size of the current valid window.
  4. Handle repeats:
    • When the character at end is not unique, increment the start pointer to shrink the window until the character becomes unique again.
    • Decrease the count of the character at start each time it is removed from the window.
  5. Repeat the process until the end pointer has traversed the entire string.

At the end, max_len will hold the length of the longest substring without repeating characters.

Python Code

def longest_substring_without_repeating(s: str) -> int:
    count = [0]*256
    start = 0
    end = 0
    max_len = 0
    while(end < len(s)):
        if count[ord(s[end])] == 0:
            max_len = max(max_len, end - start + 1)
            count[ord(s[end])]+=1
            end+=1
        else:
            while(count[ord(s[end])]!=0):
                count[ord(s[start])]-=1
                start+=1
    return max_len