Leetcode problem #1: Find longest substring without repeating characters

Problem statement

For a given input string, return length of the longest substring in the given string without repeating characters. Note: the given string includes English letters and digits.

Examples:

Example1:

Input: s = "abcabcbb"
Output: 3 (with the substring "abc")

Example 2:

Input: s = "bbbbb"
Output: 1

Example 3:

Input: s = "pwwkew"
Output: 3 (with the substring "kew")

Solution 1: Naive approach

We are using the naive approach by check every possible substring of the given string s and return the length of the longest string without repeating characters. We should follow these steps:

1. Generate all possible substrings of s by using two loops
2. When you obtain each substring, use a map to check whether there are any repeated character in this substring. If not, compare its length with length of all unique character substrings so far. If the substring has at least repeated characters, skip it.

Code example

func FindLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	max := 0
	for i := 0; i < len(s); i++ {
		visitedMap := make(map[string]bool)
		for j := i; j < len(s); j++ {
			_, found := visitedMap[string(s[j])]
			if found {
				break
			}
			max = int(math.Max(float64(max), float64(j-i+1)))
			visitedMap[string(s[j])] = true
		}
	}
	return max
}

Time complexity: O(n^3) Space complexity: O(1)

Solution 2: Sliding window

Well, it's my lovely approach ) First of all, if you have never listened about this technique, please read it in link. We should follow these steps:

1. Preparation:

• We will take 2 variables start and end to indicate a window or a substring that we are checking. Then, inititally both of them is 0 (the 0th index).
• We alse create a empty map duplicateMap to store character and its index
• We create result that we will return and initial it with value 0

2. In each iteration of end from 0 to n (is length of s), we check whether the duplicateMap has s[end] or not. If not, add s[end] and its index to the map. Otherwise, do the step 3.
3. In this step, when we have a dupplicate character, we will stop consider the current substring and do the small steps below:

• Take the length of the substring and compare with result, if the length is greater than result, update result is the length
• Update start = index of the duplicated character + 1
• Delete all keys in duplicateMap from start to index of the duplicated character

If these steps are too complex to understand or read, please see the image that show an example:

Code example (in Golang)

func FindLongestSubstringBySlidingWindow(s string) int {
	n := len(s)
	if n == 1 {
		return 1
	}
	result := 0
	duplicateMap := make(map[string]int)
	start := 0
	for end := 0; end < n; end++ {
		if idx, isDuplicate := duplicateMap[string(s[end])]; isDuplicate {
			result = int(math.Max(float64(result), float64(end-start)))

			for i := start; i <= idx; i++ {
				delete(duplicateMap, string(s[i]))
			}

			start = idx + 1
		}
		duplicateMap[string(s[end])] = end
	}
	result = int(math.Max(float64(result), float64(n-start)))
	return result
}

Time complexity: O(n) Space complexity: O(1)