Leetcode — 3. Longest Substring Without Repeating Characters (Chinese version)

Anj

4 min readDec 29, 2020

問題連結: https://leetcode.com/problems/longest-substring-without-repeating-characters/

題目要求我們在給予字串中, 找到最長且沒重複任何字元的子字串長度.

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols, and spaces.

比如在字串 “abcabcbb”中, 我們應該回傳3, 因為達成條件的最長子字串為 “abc”.

我的最初想法:

最直接的解這題的話,就直接暴力解: 跑用兩個loop來組成新子字串, 外側的loop代表我的子字串起點, 內側loop則是子字串終點, 在組成子字串後再檢查這次新增的字元有沒有重覆到目前已有的子字串中
這個方法是可行, 可是十分耗時間, 需要O(n³), 兩年前這樣的寫法在leetcode上需要428ms, 會知道是因為這是我兩年前的solution XD

所以我們來看看我們怎麼改進我們的時間複雜度. 我們再讀題目一次, 就會發現兩件事情:

我們其實不需要真的一直製造我們的子字串, 題目只要求回傳長度, 所以code不需用substring或contains來浪費時間
s only consists of English letters, digits, symbols, and spaces. 所以我們已知characters的範圍並不是無限大,而且還幸運地發現這些都是在ASCII 範圍中.

那從第一件事情, 我們就來想, 如果不真的創造子字串, 我們要怎麼知道"子字串"中到底有沒有重複的字母? 最好的辦法就是創造Map, 用Map來存字元跟其最近一次出現的index.
在Java中,我們可以用Map<Character, Integer>來達成我們的目的, 但缺點是這個時間複雜度也稍高, 兩年前我用Map做, code跑了127ms
因為如前所述的第二點, 我們可以用int array來幫忙減少時間複雜度, 已知這些字元的範圍就在ascii的前128個字元裡面, 我們可以直接設定map長度為128, for example, ‘a’的ascii是97, 最近一次出現是在i=2, map[97]就是2

(Click here to view all the characters in the ASCII table.)

以下為我的 2ms code, 今天測的時候是贏過99%的人(12/28/2020):

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n<=1)
            return n;
        int[] map = new int[128];
        Arrays.fill(map, -1);
        char[] c = s.toCharArray();
        int maxLen = 0;
        int startIndx = 0;
        for(int i=0;i<n;i++)
        {
            char cur = c[i];
            if(map[cur] >= startIndx)
                startIndx = map[cur]+1;
            maxLen = Math.max(maxLen, i-startIndx+1);
            map[cur] = i;
        }
        maxLen = Math.max(maxLen, n-startIndx);
        return maxLen;
    }
}

程式邏輯:

與其去真的存一個子字串, 我們只存子字串的開始index (i.e., startIndx)
所以我們在檢查map[cur]的時候, 我們只在乎cur有沒有出現在startIndx之後過 (因為此時的子字串的範圍就是 s.substring(startIndx,i))
如果有, 我們就會把startIndx往後移一格, 讓現在的i被包含在現在進行式的子字串, 看還有沒有機會拿到更大的子字串長度

For example, we have an input string: “advdf”.
i=0, startIndx = 0 (invisible substring is a)
i=1, startIndx = 0 (invisible substring is ad)
i=2, startIndx = 0 (invisible substring is adv)
i=3, startIndx = 1 (invisible substring is vd) (since we give up the first d, and move startIndx to the next one)
i=4, startIndx = 1 (invisible substring is vdf)

因為我們只跑一次for loop, 時間複雜度是 O(n)
空間複雜度則是常數 O(1) 😎

Leetcode — 3. Longest Substring Without Repeating Characters (Chinese version)

我的最初想法:

程式邏輯:

Written by Anj

No responses yet