Algorithms in Go: Length of the Longest Substring

Finding the length of the longest substring of a given string is a very common algorithms question in interviews. In this post, I'm going to walk you through how to solve this problem in Go.

The problem

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

Example 1:

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

Example 2:

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

Explain the solution

I'll be using a technique called sliding window. Here is how it works:

1. Iterate over the string.
2. Maintain two pointers to represent the left and right bound of a window. Both two pointers start at index 0.
3. As we iterate along the string, the right pointer acts as the looping counter, while the left pointer stays where it was, unless the right pointer encounters a character that was visited before, and the left pointer is behind the visited character. When this happens, the left pointer moves to the next iteration position.
4. To determine if a character was already visited or not, we need to maintain a hash map to store the indices of every character that the right pointer has encountered.
5. For each iteration, we calculate the window length and compare it with the previous longest length. If the current length is longer, we update the longest length record.
6. When the iteration finishes, we'll have the longest window length.

Solution

func lengthOfLongestSubstring(s string) int {
    // making a map the go way
    m := make(map[byte]int)
    res := 0

    for l, r := 0, 0; r < len(s); r++ {
        if index, ok := m[s[r]]; ok {
            // only update the left pointer if 
            // it's behind the last position of the visited character
            l = max(l, index)
        }
        res = max(res, r-l+1)
        m[s[r]] = r + 1
    }
    return res
}

func max(n, m int) int {
    if n > m {
        return n
    }
    return m
}