ac solution code


  • 0

    Solution1. Sliding Window HashSet - time = O(n); space = O(n)

    The basic idea is to use sliding window:

    1. Extend right pointer(i): if no duplicates
    2. Shrink left pointer: remove chs[left] from set until find the char same as chs[i]

    Compare and return max length of left...i

    func lengthOfLongestSubstring(_ s: String) -> Int {
        guard s.characters.count > 0 else {return 0}
        let chs = [Character](s.characters)
        var left = 0, max = 0, set = Set<Character>()
        
        for i in 0..<chs.count {
            let ch = chs[i]
            if !set.contains(ch) {                      // 1. Extend right pointer(i): if no duplicates
                set.insert(ch)                          // 1-1. Insert ch to set
                max = Swift.max(max, i - left + 1)      // 1-2. Compare length left...i and `max`
                continue
            }
            while left < i && chs[left] != chs[i] {     // 2. Shrink left pointer: remove chs[left] from set until find char same as chs[i]
                set.remove(chs[left])
                left += 1
            }
            left += 1                                   // 3. left++: skip the duplicate char
        }
        
        return max
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.