[Leetcode] 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150

initial

So I kinda reused the sliding window approach from previous question in leetcode 150

https://velog.io/@whitehousechef/Leetcode-209.-Minimum-Size-Subarray-Sum

but this was wrong approach as every problem requires a different approach. I had to debug like 5 times before i got this right.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s)==0:
            return 0
        ans = 1
        left, right = 0, 0
        check = set()
        while True:
            if right==len(s):
                break
            elif s[right] in check:
                ans = max(len(check), ans)
                check.remove(s[left])
                left += 1
            elif right < len(s):
                check.add(s[right])
                right += 1
            else:
                break
        ans = max(len(check), ans)
        return ans

solution

Firstly setting ans as 1 is wrong cuz if u have empty string, answer is 0. Secondly im updating answer in 2 different places - when i find a valid case and when i break out of the while loop. Actually, this is correct but we can just update ans when s[right] is not in check (cuz that IS the valid substring case).

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: # handle empty string edge case.
            return 0
        ans = 0
        left, right = 0, 0
        check = set()
        while right < len(s): # correct right boundary check
            if s[right] in check:
                check.remove(s[left])
                left += 1
            else:
                check.add(s[right])
                ans = max(ans, right - left + 1) # correctly calculate and update ans.
                right += 1
        return ans

revisited aug 13th 2025

I couldnt think this way in interview fuck

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> check = new HashSet<>();
        int length=0, left=0;
        String ans="";
        for(int right=0;right<s.length();right++){
            Character c = s.charAt(right);
            while(check.contains(c)){
                check.remove(s.charAt(left));
                left+=1;
            }
            if (length<right-left+1){
                length=right-left+1;
                ans=s.substring(left,right+1);   
            }         
            check.add(c);
        }
        System.out.println(ans);
        return length;
    }
}

complexity

o(n) time as set operations are o(1)
o(k) complexity where k is the substring length stored in check set but worse case it is o(n)