Non-Overlapping Substrings

Hard
0/120
profile
Contributed by
11 upvotes
Asked in companies
AmazonInspirisysGoogle inc

Problem statement

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’}.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
ab
wxzxzz
Sample Output 1 :
a b
w xzxzz
Explanation For Sample Output 1 :
For the first test case, there are two non-overlapping substrings satisfying the condition i.e. a, b.

For the second test case, we have to select the whole substring “xzxzz” for the final answer as we need to select all the occurrences of a letter in one substring. Hence the answer is w, xzxzz.
Sample Input 2 :
2
abc
xtx
Sample Output 2 :
a b c
t
Hint

For every substring try to minimize its length greedily by selecting a shorter substring having all the occurrences of all the letters in the string.

Approaches (1)
Greedy

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.
Time Complexity

O(|str|), where |str| is the length of the given string.

 

Since we are iterating through the string once. 

Hence the total time complexity is O(|str|).

Space Complexity

O( 1 ).

 

Since we are only storing the first and last indexes of 26 characters and no more space is used. 

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Non-Overlapping Substrings
Full screen
Console