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;
    }
}

Does this help? https://stackoverflow.com/questions/9734474/find-longest-substring-without-repeating-characters — Abra, Dec 31 '20 at 17:31

Unmitigated · Accepted Answer · 2020-12-31T18:09:01.713

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;
}

The question posed by the OP is not how to solve the problem, but rather what is wrong with the proposed solution they present. — John Bollinger, Dec 31 '20 at 17:34
@Abra - I see you posting such a comment on other's answers (e.g. https://stackoverflow.com/a/65445499/10819573) or on the questions which have been already been answered. There is no problem as long as you live what you say but unfortunately, that's not the case e.g. [this question](https://stackoverflow.com/q/65528040/10819573) which you answered today, has been asked several times e.g. https://stackoverflow.com/q/15916958/10819573, https://stackoverflow.com/q/8686331/10819573 etc. — Arvind Kumar Avinash, Jan 01 '21 at 16:38

Longest Substring Without Repeating Characters: Wrong answer

1 Answers1