最长字符串专题 - Githubissues

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 / algorithmbook