xzm2019

lintcode 384. 最长无重复字符的子串
给定一个字符串,请找出其中无重复字符的最长子字符串。问题分析暴力我们拿到问题,如果一时间想不到正解,可以先想想暴力...
扫描右侧二维码阅读全文
28
2019/05

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

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

问题分析

暴力

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

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

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位置处的字符就可以了。

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

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]如果被选中,那么最多可以延伸到这个字符上一次出现的位置的后一位。因此,我们可以从前到后遍历整个字符串,每次查找这个字符上一次出现的位置用来更新允许的起始点。

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

Leave a Comment