Last Updated: 20 Aug, 2021
Non-Overlapping Substrings
Hard
Asked in companies
You are given a string “str”. Find the maximum number of non-empty substrings of “str” such that no two substrings overlap with each other and each substring that you select containing a letter ‘t’ must contain all the occurrences of ‘t’ in that substring.
A string ‘a’ is a substring of a string ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
Note:
If there are multiple solutions of a string, return the string with minimum total length.
For Example :
Let str = abaccce
Now In this example, we can make a maximum of three substrings i.e. {‘b’, ‘ccc’, ‘e’}.
Note:
There can be one more solution with maximum substrings equal to three i.e. {‘aba’, ‘ccc’, ‘e’} but we have to select the substrings with minimum total length. So the final answer is {‘b’, ‘ccc’, ‘e’}.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first and only line of each test case contains a string “str”.
Output Format :
For each test case, print a list of strings “ans”.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints :
1 <= T <= 10
1 <= |str| <= 10^5, where |str| represents the length of the String str.
Time limit: 1 sec
Approaches
The approach is simple, take two arrays left and right which will store the first and last occurrences of every character of the string and we will check for each position of the string if it is the minimum possible substring satisfying the given conditions.
The steps are as follows:
- Take two vectors “first” and “last” in which we will store the first and last positions of each character in the string.
- Take a vector of strings “ans” to store all the substrings.
- Take an int “lastPos” to store the position of the last substring you inserted into the vector.
- Now iterate through the string (say iterator be i):
- Check if the current position is the first occurrence of the current letter if not then continue.
- If the current position is the first occurrence then iterate through the string from the first position to the last position(say iterator be j):
- If we found a character in “str[ j ]” which has its first position less than ‘i’ then break the loop and continue.
- Else update the last element “pos” of the substring as max( last[ s[ j ] - ’a’ ], pos).
- If “pos” is greater than “lastPos” then push the substring i to “pos” into the answer list.
- Else if “pos” is less than “lastPos” then update the last string you inserted by the current string i.e. substring i to “pos”.
- Update the “lastPos” as “pos”.
- Return the final list of strings.