Last Updated: 12 Mar, 2021
Partition Labels
Hard
Asked in companies
You are given a string ‘S’ of lowercase English letters. Your task is to partition this string into as many parts as possible so that all the occurrences of the same letter appear in exactly one of the partitions.
For example:
"qvmwtmzzse" is the given string. We can make the first two partitions as ‘q’, ‘v’, but ‘m’ can not be an individual partition because there is another occurrence of m at index 6. So, the minimum length of the third partition is from index 3 to 6 and the partition is "mwtm". Similarly, the next partitions are "zz", ‘s’, ‘e’.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line of each test case contains a string ‘S’ consisting of lowercase English letters.
Output Format:
Print the size of the partitions of the string on a single line separated by space. Note that you need to maximize the number of partitions.
Print the output of each test case in a new line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1<= T <= 10^3
1 <= |S| <= 10^3
Where |S| is the size of the given string ‘S’.
Time Limit: 1 sec
Approaches
Approach: The idea is to divide the whole string into partitions such that one partition covers all the appearances of a letter. Whenever we encounter all appearances of all the letters in the current partition is covered, then, increase the number of partitions.
The steps are as follows:
- Initialize a vector ‘ANSWER’, which stores the sizes of the partitions of the string.
- Iterate through the string from ‘i’ = 0 to |S| - 1:
- Initialize ‘LASTITHAPPEARANCE’ as -1. Iterate through the remaining string and whenever we encounter another appearance of ‘S[i]’, we update the value of ‘LASTITHAPPEARANCE’ to the current index.
- Iterate from ‘j’ = ‘i’ to 'LASTITHAPPEARANCE:
- Initialize ‘LASTJTHAPPEARANCE’ as -1. Iterate through the rest of the string and whenever we encounter the same character update the ‘LASTJTHAPPEARANCE’ to the current index.
- If the ‘LASTJTHAPPEARANCE’ is greater than ‘LASTITHAPPEARANCE’, it means the size of this partition is not sufficient to make an individual partition, it needs to be extended ie. Update ‘LASTITHAPPEARANCE’ = ‘LASTJTHAPPEARANCE’.
- When we come out of the loop, it means the partition is sufficient to make an independent partition, ie. This partition covers all the appearances of all the letters present in the partition. Make it as an individual partition and update ‘PARTITIONLEFTMOSTINDEX’ to ‘PARTITIONLEFTMOSTINDEX’ + 1 to make another partition.
- Push the length of the current partition in the answer.
- Return the array ‘ANSWER’.
Approach: The idea is to store the last appearance of each letter in an array. We can save O(N) time by doing this as we won’t have to calculate for each letter in the iteration.
The rest of the steps are similar to the previous approach.
The steps are as follows:
- Initialize a vector ‘ENDINDEX’ of size 26 with -1 (as we are having all lowercase alphabets) which stores the last appearance of each character.
- Iterate through the string from ‘i’ = 0 to |S|-1:
- Make ‘ENDINDEX[S[i] - ‘a’]’ equal to ‘i’ as we are assuming this the last index and when we encounter another appearance, we will update this value.
- Initialize a vector ‘ANSWER’, which stores the final answer.
- Initialize an integer ‘PARTITIONLEFTMOSTINDEX’ with 0, which will store the leftmost index of the current partition.
- Execute a while loop with the condition ‘PARTITIONLEFTMOSTINDEX’ is less than |S|:
- Initialize ‘PARTITIONRIGHTMOSTINDEX’ as the last appearance of the current letter ie. ‘ENDINDEX[S[PARTITIONLEFTMOSTINDEX] - ‘a’]’.
- Iterate from ‘i’ = ‘PARTITIONLEFTMOSTINDEX’ to ‘PARTITIONRIGHTMOSTINDEX’:
- Initialize ‘LASTITHAPPEARANCE’ as the last appearance of the letter ‘S[i]’. ie. endIndex[S[i] - ‘a’] as we have already stored the index of the last appearances of every letter.
- If the ‘LASTITHAPPEARANCE’ is greater than ‘PARTITIONRIGHTMOSTINDEX’, it means the size of this partition is not sufficient to make an individual partition, it needs to be extended. Update ‘PARTITIONRIGHTMOSTINDEX’ = ‘LASTITHAPPEARANCE’.
- When we come out of the loop, it means the partition is sufficient to make an independent partition, ie. this partition covers all the appearances of all the letters present in the partition. Make it as an individual partition and update ‘PARTITIONLEFTMOSTINDEX’ to ‘PARTITIONRIGHTMOSTINDEX’ + 1 to make another partition.
- Push the length of the current partition in the answer.
- Return the array ‘ANSWER’.
Similar problems