1520 LeetCode problem solution

LeetCode problem link: 1520. Maximum Number of Non-Overlapping Substrings

LeetCode 1520 problem description

Hard level problem.

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.

Example 1:

Input: s = "adefaddaccc"
Output: ["e","f","ccc"]

Explanation:
The following are all the possible substrings that meet the conditions:
[
"adefaddaccc"
"adefadda",
"ef",
"e",
"f",
"ccc",
]
If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "adefadda", we are left with "ccc" which is the only one that doesn't overlap, thus obtaining 2 substrings. Notice also, that it's not optimal to choose "ef" since it can be split into two. Therefore, the optimal way is to choose ["e","f","ccc"] which gives us 3 substrings. No other solution of the same number of substrings exist.

Example 2:

Input: s = "abbaccd"
Output: ["d","bb","cc"]

Explanation:
Notice that while the set of substrings ["d","abba","cc"] also has length 3, it's considered incorrect since it has larger total length.

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

LeetCode 1520 problem: solution explanation

We can solve this problem using Greedy + Interval Expansion patterns.

For every character, first store its first and last occurrence in s.

A valid substring that contains a character must contain all occurrences of that character. Therefore, if we start from the first occurrence of a character, the substring may need to expand when it contains other characters.

After finding a valid interval, we greedily keep non-overlapping intervals with the earliest ending position.

Step 1: Find the first and last occurrence of each character

For every character c, store:

first[c]
last[c]

For example, for:

s = "adefaddaccc"

character a appears at:

0, 4, 7

so:

first[a] = 0
last[a] = 7

Character d appears at:

1, 5, 6

so:

first[d] = 1
last[d] = 6

Characters e and f appear once:

first[e] = last[e] = 2
first[f] = last[f] = 3

Character c appears at:

8, 9, 10

so:

first[c] = 8
last[c] = 10

Step 2: Build the smallest valid interval for each possible start

We only try to start a substring at the first occurrence of a character.

Suppose:

start = first[c]
end = last[c]

Scan every character inside [start, end].

If the interval contains character x, it must contain every occurrence of x, so extend:

end = max(end, last[x])

If:

first[x] < start

the interval is invalid because x has an occurrence before the beginning of the substring.

Step 3: Example of interval expansion

For:

s = "adefaddaccc"

start with a:

start = 0
end = 7

The interval:

[0, 7] -> "adefadda"

contains all occurrences of every character inside it, so it is valid.

Now start with d:

start = 1
end = 6

While scanning [1, 6], we find a at index 4.

But:

first[a] = 0

and:

0 < 1

so the interval is invalid. It contains a, but does not contain the occurrence of a at index 0.

The remaining valid intervals are:

[2, 2]  -> "e"
[3, 3]  -> "f"
[8, 10] -> "ccc"

Step 4: Select non-overlapping intervals greedily

The valid interval:

[0, 7] -> "adefadda"

is selected first.

Then we find:

[2, 2] -> "e"

It overlaps [0, 7], but it ends earlier.

Therefore, replace:

"adefadda"

with:

"e"

An interval that ends earlier leaves more space for future non-overlapping substrings.

[3, 3] -> "f"

does not overlap "e", so we add it.

Finally:

[8, 10] -> "ccc"

also does not overlap.

The result is:

["e", "f", "ccc"]

This gives the maximum number of non-overlapping substrings and the minimum total length.

LeetCode 1520 problem: complexity

We scan s once to find the first and last occurrence of every character.

There are only 26 lowercase English letters. For each possible starting character, we may scan part of the string while expanding its interval.

Time complexity: O(26 * n), which is O(n)
Space complexity: O(1) excluding the output

Pattern: Greedy / Intervals
Technique: First and Last Occurrence / Interval Expansion

LeetCode 1520 C++ solution

class Solution {
public:
  vector<string> maxNumOfSubstrings(string s)
  {
    int n = s.size();

    vector<int> first(26, n);
    vector<int> last(26, -1);

    for(int i = 0; i < n; i++)
    {
      int c = s[i] - 'a';
      first[c] = min(first[c], i);
      last[c] = i;
    }

    vector<string> result;
    int previousEnd = -1;

    for(int i = 0; i < n; i++)
    {
      int c = s[i] - 'a';

      if(i != first[c]) continue;

      int end = last[c];
      bool valid = true;

      for(int j = i; j <= end; j++)
      {
        int x = s[j] - 'a';

        if(first[x] < i)
        {
          valid = false;
          break;
        }

        end = max(end, last[x]);
      }

      if(!valid) continue;

      if(i > previousEnd) result.push_back(s.substr(i, end - i + 1));
      else result.back() = s.substr(i, end - i + 1);

      previousEnd = end;
    }

    return result;
  }
};

LeetCode 1520 Java solution

class Solution {
  public List<String> maxNumOfSubstrings(String s) {
    int n = s.length();

    int[] first = new int[26];
    int[] last = new int[26];

    Arrays.fill(first, n);
    Arrays.fill(last, -1);

    for(int i = 0; i < n; i++) {
      int c = s.charAt(i) - 'a';
      first[c] = Math.min(first[c], i);
      last[c] = i;
    }

    List<String> result = new ArrayList<>();
    int previousEnd = -1;

    for(int i = 0; i < n; i++) {
      int c = s.charAt(i) - 'a';

      if(i != first[c]) continue;

      int end = last[c];
      boolean valid = true;

      for(int j = i; j <= end; j++) {
        int x = s.charAt(j) - 'a';

        if(first[x] < i) {
          valid = false;
          break;
        }

        end = Math.max(end, last[x]);
      }

      if(!valid) continue;

      String current = s.substring(i, end + 1);

      if(i > previousEnd) result.add(current);
      else result.set(result.size() - 1, current);

      previousEnd = end;
    }

    return result;
  }
}

LeetCode 1520 JavaScript solution

var maxNumOfSubstrings = function(s) {
  const n = s.length;

  const first = new Array(26).fill(n);
  const last = new Array(26).fill(-1);

  for(let i = 0; i < n; i++) {
    const c = s.charCodeAt(i) - 97;
    first[c] = Math.min(first[c], i);
    last[c] = i;
  }

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

  for(let i = 0; i < n; i++) {
    const c = s.charCodeAt(i) - 97;

    if(i !== first[c]) continue;

    let end = last[c];
    let valid = true;

    for(let j = i; j <= end; j++) {
      const x = s.charCodeAt(j) - 97;

      if(first[x] < i) {
        valid = false;
        break;
      }

      end = Math.max(end, last[x]);
    }

    if(!valid) continue;

    const current = s.slice(i, end + 1);

    if(i > previousEnd) result.push(current);
    else result[result.length - 1] = current;

    previousEnd = end;
  }

  return result;
};

LeetCode 1520 TypeScript solution

function maxNumOfSubstrings(s: string): string[] {
  const n: number = s.length;

  const first: number[] = new Array(26).fill(n);
  const last: number[] = new Array(26).fill(-1);

  for(let i = 0; i < n; i++) {
    const c: number = s.charCodeAt(i) - 97;
    first[c] = Math.min(first[c], i);
    last[c] = i;
  }

  const result: string[] = [];
  let previousEnd: number = -1;

  for(let i = 0; i < n; i++) {
    const c: number = s.charCodeAt(i) - 97;

    if(i !== first[c]) continue;

    let end: number = last[c];
    let valid: boolean = true;

    for(let j = i; j <= end; j++) {
      const x: number = s.charCodeAt(j) - 97;

      if(first[x] < i) {
        valid = false;
        break;
      }

      end = Math.max(end, last[x]);
    }

    if(!valid) continue;

    const current: string = s.slice(i, end + 1);

    if(i > previousEnd) result.push(current);
    else result[result.length - 1] = current;

    previousEnd = end;
  }

  return result;
}

LeetCode 1520 Python solution

class Solution:
  def maxNumOfSubstrings(self, s: str) -> List[str]:
    n = len(s)

    first = [n] * 26
    last = [-1] * 26

    for i, ch in enumerate(s):
      c = ord(ch) - ord('a')
      first[c] = min(first[c], i)
      last[c] = i

    result = []
    previous_end = -1

    for i, ch in enumerate(s):
      c = ord(ch) - ord('a')

      if i != first[c]: continue

      end = last[c]
      valid = True
      j = i

      while j <= end:
        x = ord(s[j]) - ord('a')

        if first[x] < i:
          valid = False
          break

        end = max(end, last[x])
        j += 1

      if not valid: continue

      current = s[i:end + 1]

      if i > previous_end: result.append(current)
      else: result[-1] = current

      previous_end = end

    return result