Leet code 3 — Longest Substring Without Repeating Characters

 

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

Example 1:

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

Example 2:

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

Example 3:

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 * 104
• s consists of English letters, digits, symbols and spaces.

문제 접근

이문제는 2중 for loop 으로 풀면 금방 풀리는 문제다 하지만 O(n x n)의 복잡도를 가지기 때문에 그다지 좋지 않다는 생각이 들었다.

sliding 을 사용해 O(n) 의 복잡도 로 문제를 해결 할수 있을것 같았다.

var startPoint = 0
var max = 0
val map = HashMap<Char, Int>()

1. 반복하지 않는 longest word 의 시작점을 가르킬 startPoint 를 선언 한다.
2. 가장긴 길이를 담을 max variable 를 선언한다.
3. 문자열을 각각 순회하면서 key 는 알파벳 value 는 시작점을 담을 map 을 선언한다.

for ((i, c) in s.withIndex()) {
    if (map.containsKey(c)) {
        val seekPoint = map[c]!! + 1
        startPoint = seekPoint.coerceAtLeast(startPoint)
    }
    val length = i - startPoint + 1
    max = length.coerceAtLeast(max)
    map[c] = i
}
return max

1. 현재 알파벳이 map 에 들어 있지 않으면 현재 index 에서 startPoint 를 빼고 1을 더한다. 그리고 map 에 현재 알파벳에 index 를 저장한다.

1 을 더하는 이유는 현재 index 가 0 이고 startPoint 가 0 일때 가장짧은 길이는 한글자 이기 때문에 1을 더한다.

2. 현재 알파벳이 map 에 들어 있으면 seekPoint (찾으려고 하는 알파벳의 index + 1)

과 startPoint 중 더 큰것을 startPoint 에 할당한다.