## **題目**
給定一個字符串，假設該字符串是由 26 個小寫英文字母組成，如字符串 "acbccradfr"，其最長連續不重復子串的長度為 5，對應的子串是 "cradf"。
## **思路**
動態規劃：按 C 語言習慣，索引從 0 開始。假設映射 `$ f(i) := 以第 i 個字符為結尾的子串的最長連續不重復子串的長度 $`，由此定義得知，如果第 i + 1 個字符到第 i 個字符前還沒出現過，那么 `$ f(i + 1) = f(i) + 1 $`。如果第 i + 1 個字符已經出現過，那么又有兩種情況：一種是這個字符到它上次出現時的距離```d```（索引之差）小于或等于 ```f(i)```，也就是說該字符上次出現的位置是以第 i 個字符結尾的最長連續子串的一部分，此時`$ f(i + 1) = d $`。如`$ f(2) = 3 $`，要求`$ f(3) $`，觀察知第 3 個字符 c 已經在第 1 個位置出現過一次了，因為d = 3 - 1 = 2 < f(2)，所以 `$ f(3) = 2 ("bc") $`；另一種情況是 `$ d > f(i) $`時，這意味著該字符上次出現的位置不是以第 i 個字符結尾的最長連續子串的構成部分，所以此時`$ f(i + 1) = f(i) + 1 $`。
## 代碼
``` C++
#define MAXN 26
int longestSubLength(string &str)
{
int length = str.length();
if (length == 0) {
return 0;
}
int pos[26];
memset(pos, -1, sizeof(pos));
int curLength = 0;
int maxLength = 0;
for (int i = 0; i < length; ++i) {
int p = pos[str[i] - 'a'];
// 沒出現過或距離大于f(i)
if (p < 0 || i - p > curLength) {
++curLength;
} else {
// 距離小于或等于f(i)，只有這里可能減小最長長度，所以記下之前的最長長度
if (maxLength < curLength) {
maxLength = curLength;
}
curLength = i - p;
}
}
if (maxLength < curLength) {
maxLength = curLength;
}
return maxLength;
}
```