## **题目**
给定一个字符串，假设该字符串是由 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;
}
```