LeetCode 3.Longest Substring Without Repeating Characters题目解析-wowAC

Description

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring"pwke" is a subsequence and not a substring.


题目复述

    给定一个字符串s,找出最长的没有重复字母的子串并返回该串长度。

题目解析


1.扫描法

    定义函数f(i),表示以i为开头,恰好有一个重复字母的子串的结束位置,比如abcabc,f(0)=3, f(1) = 4。如果以i开始的子串到结束位置都没有重复的字母,那么f(i) = s.length()。那么题目要求就是返回max(f(i) – i)。

    下面说明f(i)如何求解。首先可以通过扫描的方法求出f(0)。f(0)分为一下几种情况。

        1) s = "abcdefcghi", 此时f(0) = 6,显然f(1) = 6, f(2) = 6,f(3)无法确定。可以得出以下结论,以i开始的子串使得s[i – f(i)]恰好有一个重复的字母,那么对于起始位置i<j<=重复字母第一个位置,f(j) = f(i)。也可以得出最长子串不可能以j开头。

        2)s = "abcd", 此时f(0) = 4,显然f(1) = f(2) = f(3) = 4。可以得出另外一个结论,以i开始的子串使得s[i – f(i)]没有重复的字母,那么对于起始位置i<j<s.length(),都有f(j) = s.length(),此时也可以得出最长子串不可能以j为开始,在实现中我们也可以忽略f(j)的求解。

    有了上面两条结论,我们就可以得出一个O(n)的扫描算法,流程如下:

        1) 初始化i = 0, j = 0并转2)

        2)累加j直到s[i – j]恰好有一个重复字母并转3),否则转4)

        3)此时j = f(i),更新答案res = max(res, j – i),累加i并使得i指向重复字母的下一个位置并转2)

        4)此时f(i) = j = s.length(). 更新答案res = max(res, j – i)。算法结束

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i=0, j=0;
        int hash[300];
        memset(hash, 0, sizeof(hash));
        int res = 0;
        
        while(j<s.length()) {
            hash[s[j]]++;
            if(hash[s[j]] == 2) {      //对应于情况1
                res = max(res, j-i);
                while(s[i] != s[j]) {
                    hash[s[i]]--;
                    i++;
                }
                hash[s[i]]--;
                i++;
            }
            j++;
        }
        res = max(res, j-i);
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注