[LeetCode] 3. Longest Substring Without Repeating Characters [Medium]

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.

Analyse:

一開始直覺會用雙重迴圈去計算, 但結果Time Limit Exceeded...

用兩個指標: left與right去紀錄目前不重複的String,

長度length = right - left + 1;

並用一個dictionary記錄每個char最右邊的Index,

若目前right位子的char存在於dictionary,

則left = char存在於dictionary的index + 1. 直接看code會比較好理解.

Solution:

class Solution {
   
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var maxLength = 0;
        let chars = Array(s);
        var left = 0;
        var right = 0;
        var records:[Character: Int] = [:]
        
        while(right < chars.count) {
            let char = chars[right];
            
            if(records[char] != nil) {
                left = max(records[char]! + 1, left);
            }
           
            records[char] = right;
            maxLength = max(maxLength, right - left + 1);
        
            right += 1;
        }
        
        return maxLength;
    }
}