Problem of The Day: Longest Substring Without Repeating Characters

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = defaultdict(int)
        res = 0
        start = 0
        for end in range(len(s)):
            if s[end] in seen:
                start = max(start, seen[s[end]] + 1)
            res = max(res, end - start + 1)
            seen[s[end]] = end

        return res

Time: O(n) Space: O(1) if there are fixed number of characters in Alphabet. Otherwise, O(n) in general case

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int res = 0;
        Dictionary<int, int> seen = new Dictionary<int,int>();
        int start = 0;
        for(int end = 0; end < s.Length; end++) {
            if (seen.ContainsKey(s[end])) {
                start = Math.Max(start, seen[s[end]] + 1);
            }
            res = Math.Max(res, end - start + 1);
            seen[s[end]] = end;
        }
        return res;
    }
}