Maximum Number Of Non Overlapping Substrings - Leetcode Solution

Problem statement:

Given a string s, return an array of the maximum number of non-overlapping substrings that meet the following conditions:

• The substrings are non-empty and contain only lowercase English letters.
• Each substring is unique and appears only once in s.

You may return the answer in any order.

Example 1:

Input: s = "adefaddaccc" Output: ["e","f","ccc"] Explanation: The following are all the possible non-overlapping substrings that meet the conditions: [ "adefaddaccc" "adefadda", "ef", "e", "f", "ccc", "cc", "c" ] If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "adefadda" instead, then it is not possible to choose anything else.

Example 2:

Input: s = "abbaccd" Output: ["d","bb","cc"] Explanation: The following are all the possible non-overlapping substrings that meet the conditions: [ "abbaccd" "abba", "bb", "a", "c", "d", "cc", "cd" ] If we choose the first string, we cannot choose anything else and we'd get only 1. If we choose "abba" instead, we have to skip "bb" to create non-overlapping substrings, so the maximum number is 3.

Solution:

We can solve this problem using the algorithm of finding palindrome substrings. The length of the palindrome substring will be the maximum length of the non-overlapping string. We can find multiple palindrome substrings with different start and end indices. We will only select the palindrome substrings that are unique and maximize the number of non-overlapping substrings.

1. First, we will find all the palindrome substrings in a string.

2. We will create a list of unique palindrome substrings.

3. We will sort the list of palindrome substrings according to the end index.

4. We will iterate through each palindrome substring from left to right and keep track of the end index of the last selected palindrome substring.

5. We will select only those palindrome substrings whose start index is greater than the end index of the last selected palindrome substring.

6. We will add the selected palindrome substring to the result list.

7. We will update the end index of the last selected palindrome substring to the end index of the current selected palindrome substring.

8. We will return the result list.

Python code:

class Solution: def maxNumOfSubstrings(self, s: str) -> List[str]: intervals = {} for i in range(len(s)): if s[i] not in intervals: intervals[s[i]] = [i, i] intervals[s[i]][1] = i

    palindrome_subs = []
    for key in intervals:
        if len(intervals[key]) > 1:
            start, end = intervals[key][0], intervals[key][1]
            while True:
                temp_start, temp_end = start - 1, end + 1
                if temp_start < 0 or temp_end >= len(s) or s[temp_start] != s[temp_end]:
                    break
                start, end = temp_start, temp_end
            palindrome_subs.append([start, end])
    
    unique_palindrome_subs = []
    seen = set()
    for substring in palindrome_subs:
        if substring[0] not in seen:
            unique_palindrome_subs.append(substring)
            seen.add(substring[1])
    
    unique_palindrome_subs.sort(key=lambda x: x[1])
    result = []
    last_end = -1
    for substring in unique_palindrome_subs:
        if substring[0] > last_end:
            result.append(s[substring[0]:substring[1]+1])
            last_end = substring[1]
    return result

1