Partition Labels

Posted: 12 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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
Approach 1

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:

  1. Initialize a vector ‘ANSWER’, which stores the sizes of the partitions of the string.
  2. 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’.
  3. 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.
  4. Push the length of the current partition in the answer.
  5. Return the array ‘ANSWER’.
Try Problem