## **題目**
給定一個字符串,假設該字符串是由 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;
}
```