Please help as this is getting on my nerves I can't figure out what I'm doing wrong and have tried trace code.

Link to problem: https://leetcode.com/problems/longest-substring-without-repeating-characters/

I created a solution using a sliding window. It works on most test cases, but fails for a few (such as "ad"). I can't figure out where the bug is. I basically keep track in a dictionary of characters I've seen and the last index I saw them at which gets updated periodically in a loop. I use two indices i and j; i gets updated when I find a repeat character. I return the max of current max and length of current substring which is i-j. Here is my code below:

  class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            if len(s) < 2:
                return len(s) 
            m = 1
            i = 0
            j = 1
            d = {}
            d[s[0]] = 0
            while j < len(s):
                if s[j] in d and d[s[j]] >= i:
                    m = max(m, j -i)
                    i = j
                d[s[j]] = j
                j  = 1
            return max(m, j - i - 1)

Why does this fail for some cases? Example:

"au"

Output 1 Expected 2

CodePudding user response：

Last line should be return max(m, j - i). Because i is the last index we see repeated character. So. We start this index to end of the string.So length is len(s) - i . And since j = len(s) (while loop ends when j = len(s)) so last substring length is j-i. not j-i-1

And also we are updating i wrong.let's say s = "abcadf". In while loop when we see second "a" ,so j = 3, we should update i = 1, not 3. Because in this case our longest substring will start with "b".So we should update i as i = d[s[j]] 1. So final result:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) < 2:
            return len(s) 
        m = 1
        i = 0
        j = 1
        d = {}
        d[s[0]] = 0
        while j < len(s):
            if s[j] in d and d[s[j]] >= i:
                m = max(m, j -i)
                i = d[s[j]]   1
            d[s[j]] = j
            j  = 1
        return max(m, j - i)