JavaScript(ES6) divide and conquer(recursion) solution


  • 0
    A

    Inspired by: https://discuss.leetcode.com/topic/57372/java-divide-and-conquer-recursion-solution
    Trade-off space for code readability:

    const _ = { // mock lodash
      countBy: (s) => {
        const ret = {};
        for (let char of s) {
          ret[char] = (ret.hasOwnProperty(char) ? ret[char] : 0) + 1;
        }
        return ret;
      },
    };
    
    /**
     * @param {string} s
     * @param {number} k
     * @return {number}
     */
    var longestSubstring = function(s, k) {
      if (s.length < k) {
        return 0;
      }
      const countMap = _.countBy(s);
      const invalidChars = Object.keys(countMap).filter(char => countMap[char] < k);
      const substrings = s.split(new RegExp(`[${invalidChars.join()}]+`, 'g')).filter(it => it.length > 0);
      if (substrings.length === 1) {
        return substrings[0].length;
      }
      return Math.max(0, ...substrings.map(ss => longestSubstring(ss, k)));
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.