Partition String

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in companies
Media.netFlipkart limited

Problem statement

Given a string S of lowercase English letters, your task is to partition the list in as many parts as possible such that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Note 
You don’t have to print anything, it has already been taken care of. Just implement the function. 
The string will contain lowercase alphabets only.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains string S..
Output Format 
For each test case, the list containing the size of partitions will be printed.

The output of each test case is printed in a separate line.
Constraints: 
1 <= T <= 10
1 <=  N <= 5 * 10^4    
Where ‘T’ is the total number of test cases and N represents the length of the string S.
Sample Input 1:
1 
aaababcc
Sample Output 1:
6 2
Explanation of sample input 1:
The partitions are "aaabab" , "cc". The partitions are such that 'a' and 'b' appear only in the first part and 'c' appears only in the second part.
Sample Input 2:
2
ababcbacadefegdehijhklij
bbbbbb
Sample Output 2:
9 7 8
6
Explanation of sample input 2:
Test Case 1: 
The partitions are "ababcbaca" , "defegde" , 
"hijhklij".    

Test Case 2: 
The partition is "bbbbbb".
Hint

 Find the start and end index for every partition. 

Approaches (3)
Brute Force approach

The idea is to find the ending index of the current partition.Traverse the string and for the current character, find its last occurring index and check whether this value is greater than the value of last occurring index of any previous character. Update the ending index of the current partition, if required. The end of any partition will be marked if all the characters of that partition have their last occurring index less than or equal to the current index. Repeat this procedure until the end of the string and find the lengths of all the partitions made. 

Algorithm: 

 

  1. Traverse the string and for every character find it’s last occurring index in the string, check whether its last occurring index is greater than the current end. If yes, update the current end. If the current end is equal to the current index, that's the end of the current partition, store its size in list and start a new partition from next index.
  2. Return the list obtained in step 1.
Time Complexity

O(N^2), where N is the length of string S.
 

Finding the last occurring index of a character takes O(N) time. Finding the last occurring index for all the characters in the string takes O(N * N) = O(N^2) time since there are N characters in the string. Thus, the final time complexity will be O(N^2).

Space Complexity

O(N), where N is the length of the string S.
 

Since we are storing the size of all the partitions in a list, and at worst there can be N partitions, thus the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Partition String
Full screen
Console