剑指offer2之最长不含重复字的子字符串

题目(最长不含重复字符的子字符串)

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含 ‘a’-‘z’的字符。例如，在字符串 “arabcacfr” 中，最长的不含重复字符的子字符串是 “acfr”，长度为 4。

算法思路

主要采用动态规划的思想。先自顶向下分析问题，首先定义函数 f(i) 表示以第 i 个字符为结尾的不包含重复字符的子字符串的最长长度。那么从左往右扫描字符，在求 f(i) 时，我们可以从已知的 f(i-1) 推得 f(i) 的大小。 那么下面分两种情况进行讨论：

1. 如果第 i 个字符之前未出现过，那么 f(i)=f(i-1)+1，也就是直接算进以第 i 个字符为结尾的不包含重复字符的子字符串中。
2. 如果第 i 个字符之前已出现过，那么又需要分两种情况：先设第 i 个字符和它上次出现在字符串中的位置距离为 d。
   a)、当距离 d 小于等于 f(i-1)时，即第 i 个字符出现在了 f(i-1) 对应的最长字符串之中了，那么 f(i)=d,那么 f(i) 对应的最长字符串长度一定不会超过 f(i) 对应的最长字符串长度；
   b)、若这个距离 d 大于了 f(i-1) ，意味着第 i 位置上的字符出现在了 f(i-1) 对应的最长字符串的前面，则第 i 位置上的字符可以加入当前最长的字符串中，所以，f(i)=f(i-1)+1。

算法实现

算法自底向上逐步求解问题

复杂度

算法仅遍历一次字符串，因此时间复杂度为 O(n)；定义了长度为 26 的数组，空间复杂度也为 O(26)。

参考

[1] <<剑指offer2>>