1520. Maximum Number of Non-Overlapping Substrings

Problem Explanation

The problem requires to maximize the number of non-overlapping substrings that follow a rule: If a substring includes a character that character should appear only in this substring, and we only maintain the unique substring with minimal length. The input is a string of lowercase letters. The output should be an array of strings, which are the substrings.

Let's go through an example, with the string adefaddaccc, the following are all the possible substrings that meet the conditions:

1
2
3"adefaddaccc"
4"adefadda",
5"ef",
6"e",
7"f",
8"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 exists.

Approach & Algorithm

The approach that is used in the solution is greedy. First, we record the leftmost index and rightmost index of each letter. Then, for each character that appears as the leftmost in the string, if it forms a valid result(as explained above) then it must be the best result ending there.

The algorithm works as follows: Initialize the leftmost and rightmost index for each character. For each character, if it's the leftmost occurrence Check if it forms a valid solution: If it's invalid, then ignore this solution If it's valid: If this solution overlaps with the previous solution, then replace the previous solution If it does not overlap, then add this solution.

Python Solution

1
2python
3class Solution:
4    def maxNumOfSubstrings(self, s: str) -> List[str]:
5        # Get the leftmost and rightmost index for each character
6        left, right = [0] * 26, [0] * 26
7        for i in range(26):
8            left[i], right[i] = s.find(chr(i + 97)), s.rfind(chr(i + 97))
9
10        res = []
11        l = r = -1
12        for i in range(len(s)):
13            # If it's the leftmost occurrence
14            if i == left[ord(s[i]) - 97]:
15                # Check the rightmost occurrence of all characters in this substring
16                new_r = max(right[ord(c) - 97] for c in set(s[i:right[ord(s[i]) - 97] + 1]))
17
18                # If it forms a valid solution
19                if i > r:
20                    res.append(s[i:new_r + 1])
21                else:
22                    res[-1] = s[i:new_r + 1]
23                l, r = i, new_r
24        return res

Java Solution

1
2java
3class Solution {
4    public List<String> maxNumOfSubstrings(String s) {
5        int n = s.length();
6        int[] left = new int[26], right = new int[26];
7        Arrays.fill(left, n);
8        // Record the leftmost and rightmost index for each character.
9        for (int i = 0; i < n; ++i) {
10            left[s.charAt(i) - 'a'] = Math.min(left[s.charAt(i) - 'a'], i);
11            right[s.charAt(i) - 'a'] = i;
12        }
13        List<String> res = new ArrayList<>();
14        int l = -1, r = -1;
15        // For each character (if it's the leftmost occurrence),
16        // check if it forms a valid solution.
17        for (int i = 0; i < n; ++i) {
18            if (i != left[s.charAt(i) - 'a']) continue;
19            int newR = right[s.charAt(i) - 'a'];
20            for (int j = i + 1; j <= newR; ++j) {
21                if (left[s.charAt(j) - 'a'] < i) {
22                    newR = n;
23                    break;
24                }
25                newR = Math.max(newR, right[s.charAt(j) - 'a']);
26            }
27            if (newR < n && (i > r || newR < right[s.charAt(r) - 'a'])) {
28                if (i > r) res.add(s.substring(i, newR + 1));
29                else res.set(res.size() - 1, s.substring(i, newR + 1));
30                l = i;
31                r = newR;
32            }
33        }
34        return res;
35    }
36}

JavaScript Solution

1
2javascript
3var maxNumOfSubstrings = function(s) {
4    const n = s.length;
5    const left = Array(26).fill(n);
6    const right = Array(26).fill(-1);
7    for (let i = 0; i < n; ++i) {
8        left[s.charCodeAt(i) - 97] = Math.min(left[s.charCodeAt(i) - 97], i);
9        right[s.charCodeAt(i) - 97] = i;
10    }
11    let l = -1, r = -1; 
12    const res = [];
13    for (let i = 0; i < n; ++i) {
14        if (i == left[s.charCodeAt(i) - 97]) { 
15            var new_r = right[s.charCodeAt(i) - 97];
16            for (let j = i; j <= new_r; ++j) {
17                if (left[s.charCodeAt(j) - 97] < i) {
18                    new_r = n;
19                    break;
20                }
21                new_r = Math.max(new_r, right[s.charCodeAt(j) - 97]);
22            }
23            if (new_r < n && (l == -1 || r < new_r)) {
24                if (i > r && l != -1) res.pop();
25                res.push(s.substring(i, new_r + 1));
26                r = new_r;
27            }
28        }
29    }
30    return res;
31}

The above solutions present the general approach which is same for all three languages, but, the syntax is different for all. The solution first records the leftmost and rightmost index for each character and proceeds with a 'greedy' process where if it finds that the character is a leftmost occurrence, it tries to create a valid substring. If it doesn't form a valid substring, this substring is ignored. Otherwise, it is checked if this solution overlaps with the previous solution and accordingly either replaces or adds to the previous outcome.

These solutions are written in a very efficient manner, taking into account the various possibilities and conditions that can occur in the given problem. Key data structures like 'list' or 'arrays' are used for storing the necessary information for execution.

Each language solution follows good coding practices like needful comments, proper naming conventions and readable format which makes them easy to understand for anyone familiar with the respective languages.

Regardless of the language used, the key understanding lies in the logic of how substrings are formed depending on their validity and on whether or not they overlap with previous substrings. That they are solved in different common programming languages shows the universal applicability of the problem-solving logic. The mix of high-level reasoning and a deep understanding of language-specific techniques show a balanced approach to problem-solving in coding, covering a wide variety of difficulties one may face when called to code outside their comfort zone.

Overall, these solutions provide a good example of how to proceed logically with a problem, by first defining an approach and then implementing this approach using specific language functionality. The implementation is done through a smart and systematic method, carefully outlining each step and keeping track of any possible cases that could arise.

Solution Implementation