GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #1520 - Maximum Number of Non-Overlapping Substrings - LeetCode JavaScript Solutions

Back to all solutions

#1520 - Maximum Number of Non-Overlapping Substrings

Hard • View on LeetCode • View on GitHub

String Greedy

Problem Description

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[x..y], either j < x or i > y is true.
A substring that contains a certain character c must also contain all occurrences of c.

Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var maxNumOfSubstrings = function(s) {
  const charRange = new Array(26).fill().map(() => [Infinity, -Infinity]);

  for (let i = 0; i < s.length; i++) {
    const charIndex = s.charCodeAt(i) - 97;
    charRange[charIndex][0] = Math.min(charRange[charIndex][0], i);
    charRange[charIndex][1] = Math.max(charRange[charIndex][1], i);
  }

  const intervals = [];
  for (let c = 0; c < 26; c++) {
    if (charRange[c][0] === Infinity) continue;
    const start = charRange[c][0];
    let end = charRange[c][1];
    let valid = true;

    for (let i = start; i <= end; i++) {
      const charIndex = s.charCodeAt(i) - 97;
      if (charRange[charIndex][0] < start) {
        valid = false;
        break;
      }
      end = Math.max(end, charRange[charIndex][1]);
    }

    if (valid) {
      intervals.push([start, end]);
    }
  }

  intervals.sort((a, b) => a[1] - b[1] || a[0] - b[0]);

  const result = [];
  let lastEnd = -1;

  for (const [start, end] of intervals) {
    if (start > lastEnd) {
      result.push(s.slice(start, end + 1));
      lastEnd = end;
    }
  }

  return result;
};

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.