1520. Maximum Number of Non-Overlapping Substrings LeetCode Solution

In this guide, you will get 1520. Maximum Number of Non-Overlapping Substrings LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Non-Overlapping Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Number of Non-Overlapping Substrings solution in C++
Maximum Number of Non-Overlapping Substrings solution in Java
Maximum Number of Non-Overlapping Substrings solution in Python
Additional Resources

1520. Maximum Number of Non-Overlapping Substrings LeetCode Solution image

Problem Statement of Maximum Number of Non-Overlapping Substrings

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 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 <= 105
s contains only lowercase English letters.

Complexity Analysis

Time Complexity: O(26n) = O(n)
Space Complexity: |\texttt{ans}|

1520. Maximum Number of Non-Overlapping Substrings LeetCode Solution in C++

class Solution {
 public:
  vector<string> maxNumOfSubstrings(string s) {
    const int n = s.length();
    vector<string> ans;
    // leftmost[i] := the leftmost index of ('a' + i)
    vector<int> leftmost(26, n);
    // rightmost[i] := the rightmost index of ('a' + i)
    vector<int> rightmost(26, -1);

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

    auto getNewRight = [&](int i) {
      int right = rightmost[s[i] - 'a'];
      for (int j = i; j <= right; ++j) {
        if (leftmost[s[j] - 'a'] < i)  // Find a letter's leftmost index < i.
          return -1;
        // Expand the right dynamically.
        right = max(right, rightmost[s[j] - 'a']);
      }
      return right;
    };

    int right = -1;  // the rightmost index of the last substring
    for (int i = 0; i < n; ++i) {
      // the current index is the first appearance
      if (i == leftmost[s[i] - 'a']) {
        const int newRight = getNewRight(i);
        if (newRight == -1)
          continue;  // Find a letter's leftmost index < i.
        if (i <= right && !ans.empty())
          ans.back() = s.substr(i, newRight - i + 1);
        else
          ans.push_back(s.substr(i, newRight - i + 1));
        right = newRight;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */