Partition Labels

Hard
0/120
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
SamsungApple

Problem statement

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’.
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 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
Sample Input 1:
2
qvmwtmzzse
dccccbaabe
Sample Output 1:
1 1 4 2 1 1
1 4 4 1
Explanation Of Sample Input 1:
In the first test case, the given string is “qvmwtmzzse”. To maximize the number of partitions, we will make partitions as follows “q”, “v”, “mwtm”, “zz”, “s”, “e” and the lengths are 1, 1, 4, 2, 1, 1 respectively. Hence the answer is {1, 1, 4, 2, 1, 1}.

In the second test case, the given string is “dccccbaabe”. To maximize the number of partitions, we will make partitions as follows “d”, “cccc”, “baab”, “e” and the lengths are 1, 4, 4, 1 respectively. Hence the answer is {1, 4, 4, 1}.
Sample Input 2:
2
vhaagbqkaq
eaaaabaaec
Sample Output 2:
1 1 8
9 1
Explanation Of Sample Input 2:
In the first test case, the given string is “vhaagbqkaq”. To maximize the number of partitions, we will make partitions as follows “v”, “h”, “aagbqkaq” and the lengths are 1, 1, 8 respectively. Hence the answer is {1, 1, 8}.

In the second test case, the given string is “eaaaabaaec”. To maximize the number of partitions, we will make partitions as follows “eaaaabaae”, “c” and the lengths are 9, 1 respectively. Hence the answer is {9, 1}.
Hint

Iterate through the string, find the last appearance of the current letter and check if it is possible to make it an independent partition?

Approaches (2)
Greedy Approach

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’.
Time Complexity

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

 

We are iterating from the leftmost index of the string, finding the rightmost index of the current partition, and then iterating over the current partition. In each iteration, we are finding the rightmost occurrence of the current character in the current partition which contributes O(N). .  Hence, the overall time complexity is O(N ^ 2).

Space Complexity

O(1).

 

As we are using constant space.

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