Longest Substring Without Repeating Characters Problem

Question

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 

Restrictions-
Solve the question in O(n) time only.

Answer 1

We will be using sliding window here such that we will increase the size of sliding window by 1 for every unqiue char we encounter and if we encounter a seen char we shift the left side of window to seen char index + 1 .

eg : a b c a b c b b       
     ^   ^ 
     |   | 
by this point we havent encounterd any repeating char so we are just moving the right part of sliding window . Now as we encounter a repeating variable "a", we will move the left part of window to index of last 'a' + 1. 
  a b c a b c b b  
    ^   ^ 
    |   |
and so on until the right part of array finishes the input string.

class Solution:
    def lengthOfLongestSubstring(self, s):
        encountered = dict()
        anchor = length = 0
        for i, c in enumerate(s):
            if c in encountered and encountered[c] >= anchor:
                anchor = encountered[c] + 1
            else:
                length = max(length, i + 1 - anchor)
            encountered[c] = i
        return length