leetcode 3. Longest Substring Without Repeating Characters

问题

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.

思路

和考虑DP问题时的思路类似，都是基于已有的解来进行思考。

假设存在一个无重复字符子串s[i…j]，基于s[i…j+1]是否为LSWRC就可以划分为两种情况来进行讨论。

一，假设s[j+1]不存在于s[i…j]中，那么就找到一个新的从i开始的LSWRC s[i…j+1]

二，假设s[j+1]存在于s[i…j]中，记其秩为p,则s[p] == s[j+1]。那么从i开始的LSWRC长度为j-i-1，而从i+1至p开始的LSWRC长度均小于j-i-1，所以下一次将从p+1开始计算其LSWRC长度

参考代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> m;
        int i, j;
        int MAX = 0;
        for(i = 0, j = 0; i < s.length() && j < s.length(); ){
            if(m.count(s[j]) && m[s[j]] >= i){
                i = m[s[j]] + 1;
            }else{
                MAX = max(MAX, j - i + 1);
            }
            m[s[j]] = j;
            j++;
        }
        return MAX;
    }
};