Skip to content

3. Longest Substring Without Repeating Characters

Description

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

  • 0 <= s.length <= \(5 * 10^{4}\)
  • s consists of English letters, digits, symbols and spaces.

Solutions

I Sliding Window

Complexity:

  • Time complexity: \(O(n)\).
  • Space complexity: \(O(k)\), where \(k\) is the number of distinct characters in the hash table.
func lengthOfLongestSubstring(s string) int {
    maxLength := 0
    m := make(map[uint8]int)
    left := 0

    for right := 0; right < len(s); right++ {
        c := s[right]
        if i, isFound := m[c]; isFound {
            if left < i+1 {
                left = i + 1
            }
        }
        if length := right - left + 1; length > maxLength {
            maxLength = length
        }
        m[c] = right
    }

    return maxLength
}