[LeetCode] 3. Longest Substring Without Repeating Characters / Swift

[문제 보기]

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.

Example 4:

Input: s = "" Output: 0

 

Constraints:

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

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

---

슬라이딩 윈도우, 투 포인터 기법을 사용했다.

 

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var str = s.map{String($0)}
        var front = 1, rear = 0
        
        var length = 0
        
        var dict = [String: Int]()
        while front <= str.count {
            // 새로운 원소를 받는다
            let element = str[front - 1]
            if let value = dict[element] { // 이미 딕셔너리에 있는 경우
                // 현재 새로 들어온 원소가 중복되지 않을때까지 딕셔너리(윈도우)크기를 줄인다.
                for i in (rear...value) {
                    dict.removeValue(forKey: str[i])
                }
                // rear를 현재 현재 중복되기 시작한 원소까지 전진한다
                rear = value + 1
            }
            
            dict[element] =  front - 1 // 현재 element 있는 인덱스를 집어넣는다
            if front - rear > length { // 현재 부분문자열 길이를 갱신한다
                length = front - rear
            }
            
            front += 1 // front를 한칸 전진시킨다.
        }
        
        return length
    }
}