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

Given a string, find the length of the longest serial 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.

 

题目解析：意思就是找出字符串的连续递增 or 递减子串，返回该串及其长度

 

思路：

1 用另一个数组存储每一个char的“状态”；

2 正数表示递增，0表示与前一个char相同不增不减，负数表示递减；

3 如+3表示该char是第4个递增字符（从0开始）；

4 如字符串"dkggashgt"对应的状态数组如下：

     0,1,-1,0,-1,1,-1,-2,1

   记录最大 or 最小值，即为最长递增 or 最长递减串长度，对应数组下标亦为最长串最后char的数组下标；

 

代码是js写的，如下：

var lengthOfLongestSubstring = function(str) {
    if(str.length === 0) return 0;
    var maxLen = 1; //maximum serial string length
    var maxIdx = 0; //the array sub-index of the last char in the result string 
    var tmpArr = [0]; //array to save the status data
    for (var i = 1, len = str.length; i < len; i++) {
        var pa = str[i-1];
        var pb = str[i];
        var ra = tmpArr[i-1];
        if(pa>pb){
            if(ra<0){
                tmpArr.push(ra-1);
                if(-1*tmpArr[i]+1 > maxLen){
                    maxLen = -1*tmpArr[i]+1;
                    maxIdx = i;
                }

            }else{
                tmpArr.push(-1);
                if(maxLen<2){
                    maxLen = 2;
                    maxIdx = i;
                }
            }
        }else if(pa<pb){
            if(ra>0){
                tmpArr.push(ra+1);
                if(tmpArr[i]+1 > maxLen){
                    maxLen = tmpArr[i] + 1;
                    maxIdx = i;
                }
            }else{
                tmpArr.push(1);
                if(maxLen<2){
                    maxLen = 2;
                    maxIdx = i;
                }
            }
        }else{
            tmpArr.push(0);
        }
    }
    var strRet = str.slice(maxIdx-maxLen+1, maxIdx+1);//result string
    return [strRet,maxLen]; //result string and its length
};