Solution For Maximum Number Of Non Overlapping Substrings

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

Step by Step Implementation For Maximum Number Of Non Overlapping Substrings

class Solution {
    public List maxNumOfSubstrings(String s) {
        List res = new ArrayList<>();
        int n = s.length();
        int[] left = new int[n];
        int[] right = new int[n];
        Map first = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            left[i] = first.getOrDefault(c, -1);
            first.put(c, i);
        }
        first.clear();
        for (int i = n - 1; i >= 0; --i) {
            char c = s.charAt(i);
            right[i] = first.getOrDefault(c, n);
            first.put(c, i);
        }
        int j = 0, anchor = 0;
        for (int i = 0; i < n; ++i) {
            j = Math.max(j, left[i]);
            if (i == j) {
                String candidate = s.substring(anchor, i + 1);
                String valid = isValid(candidate, left, right);
                if (valid != null) {
                    if (res.size() == 0 || valid.compareTo(res.get(res.size() - 1)) > 0) {
                        res.clear();
                        res.add(valid);
                    } else if (valid.compareTo(res.get(res.size() - 1)) == 0) {
                        res.add(valid);
                    }
                }
                anchor = i + 1;
            }
        }
        return res;
    }
    public String isValid(String candidate, int[] left, int[] right) {
        int n = candidate.length();
        int j = 0;
        for (int i = 0; i < n; ++i) {
            j = Math.max(j, left[i]);
            if (i == j) {
                if (right[j] - j < n) {
                    return null;
                }
                j = right[j];
            }
        }
        return candidate;
    }
}

def maxNumOfSubstrings(s):
        # Write your code here
        # return a list of substrings
        n = len(s)
        # left[i] and right[i] represents the smallest and the largest index 
        # that contains the ith smallest character respectively
        left, right, pos = [0] * 26, [n] * 26, [0] * 26
        for i in range(n):
            c = ord(s[i]) - ord('a')
            if pos[c] == 0:
                # if the ith smallest character has not been found yet,
                # update the corresponding left and right boundary
                for j in range(c + 1, 26):
                    if pos[j] > 0:
                        # if the jth smallest character has been found,
                        # update the ith smallest character's right boundary
                        # to be the jth smallest character's left boundary
                        right[c] = min(right[c], left[j])
                left[c] = i
            pos[c] = i + 1
        # the list of substrings
        res = []
        # start represents the starting index of the current substring
        start = 0
        # end represents the ending index of the current substring
        end = 0
        for i in range(26):
            if pos[i] > 0:
                # if the ith smallest character has been found,
                # update the current substring's ending index to be the
                # ith smallest character's right boundary
                end = min(end, right[i])
                if i == end:
                    # if the current substring's ending index is equal to
                    # the ith smallest character's right boundary,
                    # meaning that the current substring does not contain
                    # any other character except for the ith smallest character,
                    # then add the current substring to the list of substrings
                    res.append(s[start: end])
                    # update the starting index of the next substring to be
                    # the current substring's ending index + 1
                    start = end + 1
        return res

/**
 * @param {string} s
 * @return {string[]}
 */
var maxNumOfSubstrings = function(s) {
    // edge case
    if (s.length === 0) {
        return [];
    }
    
    let left = 0;
    let right = 0;
    let result = [];
    
    // while loop to iterate through string
    while (left < s.length) {
        // create a set to keep track of unique characters
        let set = new Set();
        // add the first character to the set
        set.add(s[left]);
        // right pointer starts at the next character
        right = left + 1;
        
        // while loop to find the rightmost boundary
        while (right < s.length) {
            // if the set does not contain the character
            // add it and continue
            if (!set.has(s[right])) {
                set.add(s[right]);
                right++;
            } else {
                // if the set does contain the character
                // it means we have found the right boundary
                // so break out of the loop
                break;
            }
        }
        
        // right pointer is now at the right boundary
        // so we create a substring from left to right
        let substring = s.substring(left, right);
        
        // create a variable to keep track of the leftmost boundary
        // we set it to be the current left pointer
        let leftmost = left;
        
        // we iterate through the substring
        for (let i = 0; i < substring.length; i++) {
            // if the character is not the first character in the substring
            // it means we have found the new left boundary
            if (substring[i] !== substring[0]) {
                // we update the leftmost boundary
                leftmost = s.indexOf(substring[i], left);
                // and break out of the loop
                break;
            }
        }
        
        // we check if the substring is valid
        // a substring is valid if it does not overlap with any other substrings
        // we do this by checking if the right boundary of the substring is less than
        // the left boundary of any other substrings in the result
        let isValid = true;
        for (let i = 0; i < result.length; i++) {
            if (right < result[i].left) {
                break;
            } else if (right > result[i].left) {
                isValid = false;
                break;
            }
        }
        
        // if the substring is valid, we add it to the result
        if (isValid) {
            result.push({
                left: leftmost,
                right: right,
                string: substring
            });
        }
        
        // update the left pointer to be the right pointer + 1
        // this will start the next substring at the next character
        left = right + 1;
    }
    
    // we map through the result to get an array of strings
    return result.map(substring => substring.string);
};

We can solve this problem with a greedy approach. First, we sort the given array of strings in order of decreasing length. Then, we iterate through the array and for each string, we check if it can be added to our result without overlapping any of the other strings. If so, we add it to our result and continue. Otherwise, we move on to the next string.

vector maxNumOfNonOverlappingSubstrings(vector& A) {
    // sort the array in order of decreasing length
    sort(A.begin(), A.end(), [](string a, string b) {
        return a.length() > b.length();
    });
    
    // our result vector
    vector res;
    
    // iterate through the array of strings
    for (string& str : A) {
        // check if this string can be added without overlapping
        bool canAdd = true;
        for (string& s : res) {
            if (isOverlap(str, s)) {
                canAdd = false;
                break;
            }
        }
        
        // if we can add it, do so
        if (canAdd) {
            res.push_back(str);
        }
    }
    
    return res;
}

// helper function to check if two strings overlap
bool isOverlap(string& a, string& b) {
    // get the shorter and longer string
    string& s = a.length() < b.length() ? a : b;
    string& l = a.length() >= b.length() ? a : b;
    
    // iterate through the shorter string
    for (int i = 0; i < s.length(); i++) {
        // if we find a character that exists in both strings
        // at the same position, then they must overlap
        if (s[i] == l[i]) {
            return true;
        }
    }
    
    // we didn't find any overlapping characters, so they don't overlap
    return false;
}

using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Solution { 

public IList MaxNumOfSubstrings(string s) { 

//create a list to store the results 
var result = new List(); 

//create a dictionary to store the last seen index of each character 
var lastSeen = new Dictionary(); 

//create an array to store the left and right boundaries of each substring 
var boundaries = new int[2][]; 

//iterate through the string 
for (int i = 0; i < s.Length; i++) { 

//get the current character 
var c = s[i]; 

//if the character has not been seen yet, add it to the dictionary 
if (!lastSeen.ContainsKey(c)) { 
lastSeen.Add(c, i); 
} 

//if the character has been seen, update the right boundary of its substring 
else { 
boundaries[1][lastSeen[c]] = i; 
lastSeen[c] = i; 
} 
} 

//iterate through the boundaries array 
for (int i = 0; i < boundaries.Length; i++) { 

//get the current substring 
var substring = s.Substring(boundaries[i][0], boundaries[i][1] - boundaries[i][0] + 1); 

//if the substring is non-overlapping, add it to the results 
if (!result.Any(x => substring.Contains(x))) { 
result.Add(substring); 
} 
} 

return result; 
} 
}