3. Longest Substring Without Repeating Characters #

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 the length of 3.

Example 2:


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

Example 3:


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

Problem Summary #

In a string, find the longest substring without repeating characters.

Solution Approach #

This problem is similar to problems 438, 3, 76, and 567. The idea used is “sliding window”.

The right boundary of the sliding window keeps moving to the right. As long as there are no repeated characters, the window boundary continues to expand to the right. Once a repeated character appears, the left boundary needs to be shrunk until the repeated character has moved out of the left boundary, and then the right boundary of the sliding window continues to move. Repeat this process. Each movement requires calculating the current length and determining whether the maximum length needs to be updated. The final maximum value is the answer required by the problem.

Code #


package leetcode

// Solution 1: Bitmap
func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	var bitSet [256]bool
	result, left, right := 0, 0, 0
	for left < len(s) {
		// If the bitSet corresponding to the right-side character is marked true, it means this character repeats at position X; the left side needs to move forward until X is marked false
		if bitSet[s[right]] {
			bitSet[s[left]] = false
			left++
		} else {
			bitSet[s[right]] = true
			right++
		}
		if result < right-left {
			result = right - left
		}
		if left+result >= len(s) || right >= len(s) {
			break
		}
	}
	return result
}

// Solution 2: Sliding window
func lengthOfLongestSubstring1(s string) int {
	if len(s) == 0 {
		return 0
	}
	var freq [127]int
	result, left, right := 0, 0, -1

	for left < len(s) {
		if right+1 < len(s) && freq[s[right+1]] == 0 {
			freq[s[right+1]]++
			right++

		} else {
			freq[s[left]]--
			left++
		}
		result = max(result, right-left+1)
	}
	return result
}

// Solution 3: Sliding window - hash bucket
func lengthOfLongestSubstring2(s string) int {
	right, left, res := 0, 0, 0
	indexes := make(map[byte]int, len(s))
	for left < len(s) {
		if idx, ok := indexes[s[left]]; ok && idx >= right {
			right = idx + 1
		}
		indexes[s[left]] = left
		left++
		res = max(res, left-right)
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}