[ LeetCode] 3 Longest Substring Without Repeating Characters

📌 Problem

문자열이 주어졌을 때 중복되는 문자 없이 만들 수 있는 최장 길이의 부분 문자열의 길이를 구하면 된다. 이때 부분 문자열은 연속된 문자들이다.

📌 Solution

각각의 문자들을 앞에서부터 차례대로 탐색을 한다. 탐색한 문자는 앞에서부터 이어진 문자열의 마지막 문자이다. 만약 앞에서부터 이어진 문자열에 현재 탐색한 문자가 포함되어 있다면 문자열에서 중복 문자 이후부터로 문자열을 자른다. 예를 들어 abca를 보자. 4번째 문자인 a를 탐색할 때 앞에서부터 이어진 문자열은 abc이다. 이때 중복 문자인 a가 있기 때문에 이를 다음 문자인 b부터 해서 bc로 문자열을 자른다. 그리고 현재 문자인 a를 뒤에 붙여서 bca를 만든다. 이를 문자열로 구현할 수도 있지만 Map을 통해 구현할 수도 있다.

📌 Example

Example 1을 통해 이해해보자. 처음 상태는 다음과 같다.

첫 번째 문자인 a를 탐색한다. 앞선 문자열 ""에 a가 없기 때문에 a를 붙여서 "a"를 만든다. 길이는 1이다.

두 번째 문자인 b를 탐색한다. 앞선 문자열 "a"에 b가 없기 때문에 b를 붙여서 "ab"를 만든다. 길이는 2이다.

세 번째 문자인 c를 탐색한다. 앞선 문자열 "ab"에 c가 없기 때문에 c를 붙여서 "abc"를 만든다. 길이는 3이다.

네 번째 문자인 a를 탐색한다. 앞선 문자열 "abc"에 a가 있기 때문에 a 이후인 "bc"로 문자열을 자르고 a를 붙여서 "bca"를 만든다. 길이는 3이다.

다섯 번째 문자인 b를 탐색한다. 앞선 문자열 "bca"에 b가 있기 때문에 이후인 "ca"로 문자열을 자르고 b를 붙여서 "cab"를 만든다. 길이는 3이다.

여섯 번째 문자인 c를 탐색한다. 앞선 문자열 "cab"에 c가 있기 때문에 이후인 "ab"로 문자열을 자르고 c를 붙여서 "abc"를 만든다. 길이는 3이다.

일곱 번째 문자인 b를 탐색한다. 앞선 문자열 "abc"에 b가 있기 때문에 이후인 "c"로 문자열을 자르고 b를 붙여서 "cb"를 만든다. 길이는 2이다.

여덟 번째 문자인 b를 탐색한다. 앞선 문자열 "cb"에 b가 있기 때문에 이후인 ""로 문자열을 자르고 b를 붙여서 "b"를 만든다. 길이는 1이다.

결과적으로 미중복 최장 길이 부분 문자열의 길이는 3이다.

📌 Code

fun lengthOfLongestSubstring(s: String): Int {
    var start = 0
    val map = HashMap<Char, Int>()
    return s.toCharArray().mapIndexed { index, ch ->
        start = max(start, (map[ch] ?: -1) + 1)
        map[ch] = index
        return@mapIndexed index - start + 1
    }.maxOrNull() ?: 0
}