Longest Substring Without Repeating Characters

1. Problem Description

Given an array arr, return the length of the longest subarray without repeated elements in arr (no repetition means all numbers are different).

2. Approach

1. Approach 1
   • While traversing, use a set to track whether an element exists. If not, increment the count; if it does, start counting again.
2. Approach 2
   • Two pointers

3. Implementation

3.1. set

func lengthOfLongestSubstring(s string) int {
    maxCount := 0
    for i := 0; i < len(s); i++ {
        visited := make(map[byte]bool, 0)
        count := 0
        for j := i; j < len(s); j++ {
            if visited[s[j]] {
                break
            }
            visited[s[j]] = true
            count++
            maxCount = max(maxCount, count)
        }

    }
    return maxCount
}


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

3.2. Two Pointers

func maxLength2(arr []int) int {
	if len(arr) == 0 {
		return 0
	}
	m := make(map[int]int, 0)
	max := 1

	start := 0
	end := 0
	for end < len(arr) {
		if _, ok := m[arr[end]]; ok {
			start = Max(start, m[arr[end]]+1)
		}
		max = Max(max, end-start+1)
		m[arr[end]] = end
		end++
	}

	return max
}

func Max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

4. References

• Longest Substring Without Repeating Characters - NowCoder