Skip to content

3. Longest Substring Without Repeating Characters

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

c++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int result = 0;

        for (int i = 0, j = 0; j < s.length(); j++) {
            char c = s[j];
            if (map.find(c) != map.end()) {
                i = max(map.at(c), i);
            }
            result = max(result, j - i + 1);
            map[c] = j + 1;
        }

        return result;
    }
};
go
func max(x int, y int) int {
    if x >= y {
        return x
    }
    return y
}

func lengthOfLongestSubstring(s string) int {
    lookup := make(map[uint8]int)
    answer := 0

    for i, j := 0, 0; j < len(s); j++ {
        ch := s[j]
        if _, ok := lookup[ch]; ok {
            i = max(lookup[ch], i)
        }
        answer = max(answer, j-i+1)
        lookup[ch] = j + 1
    }

    return answer
}
js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  var map = {}
  var ans = 0

  for (let i = 0, j = 0; j < s.length; j++) {
    let ch = s[j]

    if (map[ch] !== undefined) {
      i = Math.max(map[ch], i)
    }

    ans = Math.max(ans, j - i + 1)
    map[ch] = j + 1
  }

  return ans
}
py
class Solution(object):

    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup, ans, i = {}, 0, 0

        for j, c in enumerate(s):
            if c in lookup:
                i = max(lookup[c], i)
            ans = max(ans, j - i + 1)
            lookup[c] = j + 1

        return ans