最长字符串专题

[RubyLouvre]

3. Longest Substring Without Repeating Characters

找到字符串不出现重复字符的最长子串的长度。

滑动窗口法

 function lengthOfLongestSubstring(s) {
      var max = 0, left = 0, right = 0;
      var n = s.length;
      var hash = {}
      while (left < n && right < n) {
        if (!hash[s[right]]) { //right不断前进，碰到重复的，left才往前走一步
          hash[s[right]] = true
          //only test
          if (right - left + 1 > max) {
            console.log(s.slice(left, right + 1))
          }
          max = Math.max(max, right - left + 1);
          right++;
        } else {
          hash[s[left]] = false
          left++;
        }
      }
      return max
    };

滑动窗口法的优化

我们从左到右遍历，用hash大法记录每个字符第一次出现的位置，记录这个不断变长的子串的长度，默认它就是最大的。当我们遇到一个重复字符出现 在hash中，我们需要退回这个字符上次的出现的位置的后一位，然后获取这个字符到重复字符的子串，比如它们的大小。

这说得有点抽象，看一下字符串abcdaefghbkji123, 我们第一个子串是abcd, 再前进就碰到a，因此需要改到上一个a的位置的后面，重新截取一个子串，得到bcdae时，长度就大于abcd，然后就是不断增大这个子串。

但怎么增大呢，我们可以通过记录一个left变量，及一个不断往后走的right变量，就可以得到s.slice(left, right+1)子串。

下面是答案, 我们把每次碰到重复字符串，得到的子串也显示出来了。

 function lengthOfLongestSubstring(str) {
      //abcdakijuopk
      var len = str.length, max = 0, hash = {}
      for (var right = 0, left = 0; right < len; right++) {
        var word = str[right];
        if (hash[word]) {
          //如果出现重复字符, left从零挪到第一个重复的字符的后面（已加1）
          left = Math.max(hash[word], left);
        }
        if (right - left + 1 > max) {
          max = right - left + 1
          console.log(str.slice(left, right + 1), '======')
          // max = Math.max(max, right - left + 1);//left会减多1，因此要加1
        }
        // 记录right的位置，right至少比left大1，贴在它后面
        // console.log(word, max, str.slice(left, right+1))
        hash[word] = right + 1;
      }
      return max;
    };
console.log(lengthOfLongestSubstring('abcdaefghbkji123'))
console.log(lengthOfLongestSubstring('abcabcbb'))
console.log(lengthOfLongestSubstring('pwwkew'))

该算法的时间复杂度为O(n),空间复杂度为O(1)

159. Longest Substring with At Most Two Distinct Characters

求一个包括最多2种字母的最长子串

Example 1:

Input: “eceba”
Output: 3
Explanation: t is “ece” which its length is 3.
Example 2:

Input: “ccaabbb”
Output: 5
Explanation: t is “aabbb” which its length is 5.

我们需要一个hash记录每个字符出现的次数，当字符的数量超过两个，那么需要移动left，将left所指向的那种字符全部删掉。

function lengthOfLongestSubstringTwoDistinct(s) {
      var res = 0, left = 0;
      var m = {}
      for (var right = 0; right < s.length; right++) {
        var c = s[right]
        m[c] = m[c] ? m[c] + 1 : 1

        while (Object.keys(m).length > 2) {
          if (--m[s[left]] == 0) {
            delete m[s[left]]
          }
          ++left;
        }
        res = Math.max(res, right - left + 1);
      }
      return res;
 };

另一种解法，不使用哈希

function lengthOfLongestSubstringTwoDistinct(s) {
      if (!Object(s).length) {
        return 0;
      }
      var count = 0, first = -1, second = -1;
      for (var i = 0; i < s.length; i++) {
        if (first == -1) {
          first = i;
        }
        var third = s[i]
        if (second == -1 && third != s[first]) {
          second = i;
        }

        if (third != s[first] && third != s[second]) {
          count = Math.max(count, i - first);
          first = second;
          second = -1;
          i = first;
        }
      }
      return Math.max(count, s.length - first);
    };


    console.log(lengthOfLongestSubstringTwoDistinct('eceba'))
    console.log(lengthOfLongestSubstringTwoDistinct('ccaabbb'))

340. Longest Substring with At Most K Distinct Characters.

求一个包括最多K种字母的最长子串

function lengthOfLongestSubstringKthDistinct(s, k) {
      var res = 0, left = 0;
      var m = {}
      for (var right = 0; right < s.length; right++) {
        var c = s[right]
        m[c] = m[c] ? m[c] + 1 : 1

        while (Object.keys(m).length > k) {
          if (--m[s[left]] == 0) {
            delete m[s[left]]
          }
          ++left;
        }
        res = Math.max(res, right - left + 1);
      }
      return res;
    };


    console.log(lengthOfLongestSubstringKthDistinct('ecebbace', 3))
    console.log(lengthOfLongestSubstringKthDistinct('cccaabbbr', 3))

395. Longest Substring with At Least K Repeating Characters

要求是找出最长的子串，子串中的每一个字符都要重复至少k次。

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元素一定不在子字符串中，只需要将其作为分界点，分别找出左半部分和右半部分的满足条件的最长子字符串。

Input:
s = "aaabb", k = 3

Output:
3

Input:
s = "ababbc", k = 2

Output:
5

      function longestSubstring( s,  k) {
	    return longestSubstringSub(s, k, 0, s.length - 1);
	}
 
	 function longestSubstringSub( s,  k,  start,  end){
	    if(start > end) return 0;
	    var count = new Array(26).fill(0)
	    for(var i = start; i <= end; i++){
	        count[s.charCodeAt(i)- 97]++;
	    }
	    for(var i = 0; i < 26; i++){
	        if(count[i] > 0 && count[i] < k){
	            var pos = s.indexOf( String.fromCharCode(i+97), start);
	            return Math.max(longestSubstringSub(s, k, start, pos - 1), longestSubstringSub(s, k, pos + 1, end));
	        }
	    }
	    return end - start + 1;
	}

[RubyLouvre]

var minWindow = function(s, t) {
	var hash = {}
	for(var i = 0; i < t.length; i++){
		hash[t[i]] = 0;
	}
	var ret = '' 
	var left = 0, right = 0
    while(right < s.length){
		    var match = false
			if(s[right] in hash){
				console.log("命中",s[right])
				match = true
                for(var r in hash){
					if(!hash[r]){
						match = false
					}
				}
			}
            if(match){
				while(!(s[left] in hash)){
                     left++
				}
				if(!ret ||ret.length > s.slice(left, right+1)){
					ret = s.slice(left, right+1)
				}
				right++

			  //  console.log(s.slice(left, right+1), Object.assign({}, hash))
			
				//break
            }else{
				if(right - left < t.length){ // 如果长度不够
					right++ //向右移动
					if(hash[s[right]] >= 0){
				       hash[s[right]]++
					}
				 
				}else{ //长度够了，但没有命中，
					if(	hash[s[left]] > 0){
						hash[s[left]]--
					}
					console.log("left向前")
				    left++
				}
			}	
		
	}
    return ret;
};