Last Updated: 19 Dec, 2020
Partition String
Moderate
Asked in companies
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.
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.
Approaches
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:
- 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.
- Return the list obtained in step 1.
The problem says to partition the string, so finding the first and last occurrence of each character of the string, we get some intervals. Merge the overlapping intervals and store their lengths in a list and return it.
Algorithm:
- Traverse through the given string and for every character, present in the string, find its first occurring index and the last occurring index and store it .
- In step 1, we have got a list of intervals, merge the overlapping intervals .
- Find the size of each interval after merging in step 2. Store these sizes in a list
- Return the list created in step 3.
The idea is to find the ending index of the current partition. Precompute the last occurring index for all characters by traversing the string and storing every character’s last occurring index in a list. Again traverse the string and for the current character get its last occurring index from the precomputed list 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:
- Traverse the string and store every character’s last occurring index.
- Again traverse the string and for every character 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.
- Return the list obtained in step 2.