tags: String

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 subsequence and not a substring.

Function:

public int lengthOfLongestSubstring(String s) {
    // Your Code
}

題目分析

該題目是字符串類型的Medium題目，要求尋找字符串中最長的不重復(fù)子串。想尋找字符串中的最長子串，肯定需要遍歷整個字符串，那么最優(yōu)化算法的時間復(fù)雜度也必須是O(n)。下面介紹兩個算法：算法1是一個樸素想法的實現(xiàn)，算法效率較低；算法2是一個時間復(fù)雜度為O(n)的實現(xiàn)，具有很高的算法效率和算法實現(xiàn)的可借鑒性。

算法1：自己的實現(xiàn)

public int lengthOfLongestSubstring(String s) {
    int result = 0;
    Queue<Character> qc = new LinkedList<>();
    int sLength = s.length();
    for (int i=0; i<sLength; i++) {
        char ch = s.charAt(i);
        if (qc.contains(ch)) {
            if (result < qc.size())
                result = qc.size();
            while (qc.contains(ch)) { // 1. 這里不應(yīng)該用contains方法
                qc.remove();
            }
        }
        qc.add(ch);
    }
    if (qc.size() > result)
        result = qc.size();
    return result;
}

算法1的想法很樸素，建立一個不重復(fù)的字符串隊列，遍歷傳入的字符串s，如果下一個字符在當(dāng)前隊列中已存在，則判斷隊列是否是當(dāng)前最長子串，然后依次移除隊頭的字符直到隊列不存在重復(fù)字符。這樣完成一次遍歷后，就可以找到最長子串。下面分析一下以上實現(xiàn)的時間效率：LinkedList的contains方法是需要遍歷隊列（只要不是索引結(jié)構(gòu)，哪種數(shù)據(jù)結(jié)構(gòu)都需要遍歷），每嘗試放入一個字符，該方法都需要遍歷一次隊列，很顯然這是一個時間復(fù)雜度為O(n2)的實現(xiàn)。另外這份代碼中還存在一個性能問題：

1. 無論是LinkedList 或 ArrayList，甚至是除索引結(jié)構(gòu)（如hash、字典樹等）以外的數(shù)據(jù)結(jié)構(gòu)的contains方法肯定需要以某種順序遍歷數(shù)據(jù)內(nèi)容，所以能少用盡量少用。

算法2：高效的算法

public int lengthOfLongestSubstring(String s) {
    int lastIndices[] = new int[256]; // int數(shù)組模仿hash table
    for(int i = 0; i<256; i++){
        lastIndices[i] = -1;
    }

    char[] chArray = s.toCharArray();
    int strLen = chArray.length;
    int maxLen = 0;
    int curLen = 0;
    int start = 0; // 不重復(fù)子串起點字符的index
    for(int i = 0; i<strLen; i++){
        char cur = chArray[i];
        if(lastIndices[cur]  < start){
            lastIndices[cur] = i;
            curLen++;
        }
        else{
            int lastIndex = lastIndices[cur]; // 獲取重復(fù)字符位置，更新子串起點
            start = lastIndex+1;
            curLen = i-start+1;
            lastIndices[cur] = i;
        }

        if(curLen > maxLen){
            maxLen = curLen;
        }
    }

    return maxLen;
}

算法1的分析中說明了其效率低的原因，是每次加入一個字符時都需要重新遍歷隊列，確保子串的不重復(fù)性。算法2針對這一點，利用hash結(jié)構(gòu)——lastIndices數(shù)組——取代了隊列的遍歷，當(dāng)遍歷新的字符時，首先查看該字符是否在當(dāng)前子串中出現(xiàn)過，即lastIndices[cur] ? start，如果沒出現(xiàn)，則直接更新該字符的lastIndices信息；如果出現(xiàn)過，需要同時更新start和lastIndices信息。并在遍歷過程中更新最長子串長度。很顯然，算法2的時間復(fù)雜度為O(n)，超過Java AC的90%。

總結(jié)

該題目AC的難度不大，算法1雖然效率明顯不如算法2，但也是AC的。不過算法2有很值得借鑒的地方：

• 對于需要遍歷的地方，應(yīng)考慮用索引結(jié)構(gòu)（如hash）提高效率。