LeetCode 3. Longest Substring Without Repeating Characters [Swift 题解]

题目

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

Example 1:

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

Example 2:

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

Example 3:

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

思路

有点类似sliding window problem, 用一个dictionary来记录character出现的index, 然后有一个variable 来记住上一个重复的字母的位置。 Iterate的时候每次即可以求出符合条件的最长substring

class Solution {  
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var dict = [Character: Int]()
        var lastRepeatPosition = -1
        var longest = 0

        for (index, char) in s.enumerated() {
            if let index = dict[char], index > lastRepeatPosition {
                lastRepeatPosition = index
            }

            dict[char] = index
            longest = max(index - lastRepeatPosition, longest)
        }

        return longest
    }
}

chenbo

编程爱好者

Singapore