New update is available. Click here to update.

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