CodeHub: 2014

題目:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

想法 :

Brute-force:設字串長度為 n, 考慮所有數對 (i, k), 0 <= i < n, 0 < k <= n - i，檢查以 s[i] 起頭，長度為 k 的子字串是否滿足條件，並記下長度，再回傳其最大值。直接了當，時間複雜度為 O(n^2)，於目前測資來看，必定超時。

DP: 使用大小為 256 的整數陣列 buffer 來記錄各字母出現的位置。同樣考慮數對 (i, k)，在掃過字串時，更新 (i, k) 。假設目前掃到的足標為 j ，此時有兩種情形

s[j] 未在 (i, k) 代表的子字串出現過，即 buffer[s[j]] < i，++k 後繼續下一個文字。
s[j] 已在 (i, k) 代表的子字串出現過，即 buffer[s[j]] >= i，記下當下長度 k ，更新 i 為 buffer[s[j]] + 1(因 s[buffer[j]] 與 s[j] 相同，起點為 buffer[j] 之前，長度為 k 的子字串必包含相同文字)，更新 buffer[s[j]] = j。 k 之最大值即為所求。時間複雜度為 O(n)，空間複雜度為 O(m)，m 為字串中可能出現的字母種類數。

code:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) {
            return 0;
        }
    
        int usedChars[256] = {0};
    
        for (size_t i = 0; i < 256; ++i) {
            usedChars[i] = -1;
        }
    
        int ret = 0;
        int length = 0;
        int start = 0;
    
        for (int i = 0; i < s.size(); ++i) {
            ++length;
    
            if (usedChars[s[i]] >= 0 && usedChars[s[i]] >= start) {
                start = usedChars[s[i]] + 1;
                length = i - usedChars[s[i]];
            }
            usedChars[s[i]] = i;
    
            ret = std::max(ret, length);
        }
    
        return ret;
    }
    
};

以下環境為 OSX 10.9.4 + ADT 的設置心得。

只在 Eclipse 的偏好設定裡設置 NDK 位置 project 是可以直接編譯過，

但是 Eclipse 的 C/C++ source indexer 會掛掉，掛掉你一開 *c, *cpp source codes，

Eclipse 就跟你靠背 project 有 error 不讓你執行，雖然可以手動刪掉 error message，

但總不能一開 *.c, *.cpp 就要刪一次錯誤訊息吧...

此問題的主因是 android NDK 的 toolchain 針對 C/C++ indexer 支援並不完整，

所以要更換 toolchain 為 linux GCC ，但是編譯依然由 ndk-build 執行。