Longest Substring Without Repeating Characters: Wrong answer

Question

I have sent hours trying to find out the reason why the method returns a wrong answer for this particular test case: "qrsvbspk". The method returns 6 instead of 5. I cannot figure out what is wrong. Plz help!

Here's my approach:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0;
        int max_count = -1;
        int count = 0;
        
          if(s.length() == 0)
              return 0;
        
        HashSet<Character> set = new HashSet();
        
        int k = 0;
        while(k < s.length()){
            i = k;
            while(i < s.length() && !set.contains(s.charAt(i))){
                count++;
                set.add(s.charAt(i++));
            }
            if(count >= max_count){
                max_count = count;
                set.clear();
                count = 0;
            } 
                k++;
        }
        return max_count;
    }
}

Answer 1

Your approach is not correct because you only clear the Set and reset the count if a longer substring is found, when you should be doing that on each iteration of the outer loop.

You can use a two-pointers approach for increased efficiency. As the left pointer moves from 0 the the 1 less than the length of the String, we keep increasing the right pointer until we reach a character that is already in the Set. After that, the length of the current substring is right - left and we remove the character at the left index from the Set. Since both pointers can be increased at most N times (where N is the length of the String), this approach runs in O(N).

public int lengthOfLongestSubstring(String s) {
    int max_count = 0;
    HashSet<Character> set = new HashSet();
    int left = 0, right = 0;
    while(left < s.length()){
        while(right < s.length() && set.add(s.charAt(right))){
            ++right;
        }
        max_count = Math.max(max_count, right - left);
        set.remove(s.charAt(left++));
    }
    return max_count;
}