lintcode 384. 最长无重复字符的子串

xzm2019

May 28, 2019

2120views

No comments

2577字数

算法

> 给定一个字符串，请找出其中无重复字符的最长子字符串。

## 问题分析

### 暴力

我们拿到问题，如果一时间想不到正解，可以先想想暴力的做法，再一步一步优化。

最暴力的做法是：枚举这个子串的起始点`st`和终止点`en`，然后扫一遍这个子串判断里面有没有重复的字符。如果这个子串中没有重复字符，说明该子串合法，我们就取当前的长度`en - st + 1`，和当前答案取最大值`max`。

```cpp
class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    int lengthOfLongestSubstring(string &s) {
        int len = s.size();
        int nums[255] = {0};
        int nowmax = 0;
        for (int i = 0; i < len; i++){
            for (int j = i; j < len; j++){
                memset(nums, 0, sizeof(nums));
                bool flag = true;
                for (int k = i; k <= j; k++)
                {
                    if (nums[s[k]]++ >= 1){
                        flag = false;
                        break;
                    }
                }
                if (flag){
                    nowmax = max(nowmax, j - i + 1);
                }
            }
        }
        return nowmax;
    }
};
```

这样的做法是最朴素暴力的做法，时间复杂度是$O(n^3)$，显然不能通过这个题目。

### 进一步优化

我们发现，对于字符是否重复的判断中，在固定住起始点`st`时，如果终止点是`en`的话，即当前统计`st~en`的子串，那么该子串的子串`st~en-1`已经在上一步中统计过了，所以我们可以直接把上一步中的结果拿过来，在此基础上加上`en`位置处的字符就可以了。

也就是说，我们在固定住起点，枚举终止点的时候可以把终止处的字符一步步加入进去进行判断。该过程甚至可以在此剪枝，即如果当前已经不满足所有的字符都只存在一次，那么再枚举终止位置也就没有意义了，此时就可以枚举下一个起始位置了。

```cpp
class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    int lengthOfLongestSubstring(string &s) {
        int len = s.size();
        int nums[255] = {0};
        int nowmax = 0;
        for (int i = 0; i < len; i++){
            memset(nums, 0, sizeof(nums));
            for (int j = i; j < len; j++){
                if (nums[s[j]]++ >= 1){
                    break;
                }
                nowmax = max(nowmax, j - i + 1);
            }
        }
        return nowmax;
    }
};
```

这样的优化可以让我们的时间复杂度下降到$O(n^2)$，已经可以通过此题。

### Challenge：终极优化

在上一步优化里，我们对右端点进行了优化，于此同时我们也可以考虑在左端点上进行一部分优化。

我们考虑到题目要求找不含重复字符的子串，那么对于每一个字符`s[i]`如果被选中，那么最多可以延伸到这个字符上一次出现的位置的后一位。因此，我们可以从前到后遍历整个字符串，每次查找这个字符上一次出现的位置用来更新允许的起始点。

```cpp
class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    int lengthOfLongestSubstring(string &s) {
        int len = s.size();
        int last[255];
        int st = 0;
        int nowmax = 0;
        memset(last, -1, sizeof(last));
        for (int i = 0; i < len; i++){
            st = max(st, last[s[i]] + 1);
            nowmax = max(nowmax, i - st + 1);
            last[s[i]] = i;
        }
        return nowmax;
    }
};
```
这样时间复杂度最后可以被下降为$O(n)$。

Last modification：May 28th, 2019 at 09:03 pm

If you think my article is useful to you, please feel free to appreciate

lintcode 384. 最长无重复字符的子串