3. Longest Substring Without Repeating Characters

문제

Medium

 

Description

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

 

Examples

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

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

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

 

Constraints

• 0 <= s.length <= 5 * 10⁴
• s consists of English letters, digits, symbols and spaces.

 

Solution : Sliding Window Optimized

1. 문자의 인덱스를 저장할 배열을 만든다. (key가 int일 때, string에 비해 실행속도가 더 빠르다.)
2. l은 substring의 시작 문자를 가리킨다. r은 substring의 끝 문자를 가리킨다
3. 두 개의 인덱스(l, r)를 가지고 문자열을 끝에 도달할 때까지 순회한다.
   1. r을 이동하면서 r이 가리키는 문자가 l과 r 사이에 등장한 적 있는지 확인한다.
      1.  등장한 적 있다면, l을 배열의 값으로 업데이트한다
   2. 현재까지의 substring의 길이는 r - l +1이다
   3. 배열에 r이 가리키는 문자를 key로, r+1을 value로 넣는다. (r+1 : l이 이동해야할 위치)
4. 가장 컸던 substring의 길이를 반환한다.

 

(english)

1. Create an array to store the indices of characters (using int keys for the array is faster than using string keys).
2. Let l indicate the start character of the substring and r indicate the end character of the substring.
3. Use these two indices to iterate through the given string until the end is reached.
   
   1. While advancing r, check if the chacater at r has appeared between l and r before.
      1. If it has, update l to the value of the array at the corresponding index.
   2. The current length of the substring is r - l + 1.
   3. Insert a key-value pair into the array, where the key is the character at r, the value is r+1. (i.e., the position where l will move)
4. Return the maximum length of the substring found.

 

Code (Go)

func lengthOfLongestSubstring(s string) int {
	result := 0

	n := len(s)
	charIdxMap := map[int]int{} // [char(int)]index
	for l, r := 0, 0; r < n; r++ {
		right := int(s[r])
		if newLeftIndex := charIdxMap[right]; l < newLeftIndex {
			l = newLeftIndex
		}

		curResult := r - l + 1
		if curResult > result {
			result = curResult
		}
		charIdxMap[right] = r + 1
	}

	return result
}

 

Complexity Analysis

시간 복잡도 : O(n)

    문자열의 처음부터 끝까지, 한번만 순회하게 된다.

 

공간 복잡도 : O(n)

    추가적으로 생성한 배열에 방문한 문자들을 원소로 넣는다. 해당 배열의 최댓값은 문자열의 길이와 같다.

 

(english)

Time complexity: O(n)

    We traverse the string containing n elements only once. Each lookup in the table costs only O(1) time.

Space complexity: O(n)

    The extra space required depends on the number of items stored in the array, which stores at most n elements.