3. Longest Substring Without Repeating Characters

Đề bài

Cho một chuỗi, hãy tìm độ dài của chuỗi con (substring) dài nhất mà không có ký tự lặp lại.

Ví dụ 1:

Input: "abcabcbb"
Output: 3
Giải thích: Đáp án là "abc", có độ dài bằng 3.

Ví dụ 2:

Input: "bbbbb"
Output: 1
Giải thích: Đáp án là "b", có độ dài bằng 1.

Ví dụ 3:

Input: "pwwkew"
Output: 3
Giải thích: Đáp án là "wke", có độ dài bằng 3.
Lưu ý: đáp án bắt buộc phải là **chuỗi con (substring)**, nên "pwke" chỉ là **dãy con (subsequence)** chứ không phải substring.

Tóm tắt đề

Trong một chuỗi, hãy tìm chuỗi con dài nhất mà các ký tự không bị trùng lặp.

Ý tưởng

Bài này rất “kinh điển” và thường được giải bằng cửa sổ trượt (sliding window) (tương tự một số bài dạng chuỗi khác).

Ta dùng 2 con trỏ để biểu diễn một cửa sổ $[left, right]$:

• Mở rộng: Dịch right sang phải. Nếu ký tự mới chưa xuất hiện trong cửa sổ hiện tại thì cứ mở rộng tiếp.
• Thu hẹp: Khi gặp ký tự bị lặp, ta dịch left sang phải để “loại” ký tự lặp ra khỏi cửa sổ (cho tới khi cửa sổ trở lại hợp lệ).

Mỗi lần cập nhật cửa sổ, ta tính độ dài hiện tại và cập nhật đáp án lớn nhất. Kết quả cuối cùng chính là độ dài chuỗi con dài nhất không lặp.

Code

package leetcode

// Cách 1: Dùng mảng đánh dấu (như "bitset")
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) {
		// Nếu ký tự bên phải đã xuất hiện trong cửa sổ, cần dịch left để bỏ ký tự lặp
		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
}

// Cách 2: Cửa sổ trượt (sliding window) với mảng tần suất
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
}

// Cách 3: Cửa sổ trượt + hash map lưu vị trí xuất hiện gần nhất
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
}

---