Max Gold DSA Problem Solution

Partition Labels DSA Problem Solution

by

In this post, we are going to solve Partition Labels DSA Problem from Flipkart Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

Partition Labels DSA Problem Statement

You are given a string

S consisting of

n lowercase Latin letters. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be

S.

Print a list of integers representing the size of these parts.

Input

The first line of input contains an integer

t

(1≤t≤104) — the number of testcases. The description of

t testcases follows.

The first and only line of each testcase contains a string

S

(1≤|S|≤105).

It is guaranteed that the sum of

|S| over all testcases does not exceed

105.

Output

For each test case, print the list of partition sizes in a single new line.

Example
Input
2
ababcbacadefegdehijhklij
eccbbbbdec
Output
9 7 8 
10 

Note
In sample test case 1, The partition is 
“ababcbaca”, 
“defegde”, 
“hijhklij”. This is a partition so that each letter appears in at most one part. A partition like 
“ababcbacadefegde”, 
“hijhklij” is incorrect, because it splits 
S into less parts.
Problem Solution C++
#include <bits/stdc++.h>
using namespace std;

int main() {

int t;
cin>>t;
while(t--){
string s;
cin>>s;
//cout<<s<<endl;
int n=s.length();

vector<int>a(26,0);
for(int i=0;i<n;i++){
a[s[i]-'a']=i;
}

int j=0,anc=0;
vector<int>ans;

for(int i=0;i<n;i++){
j=max(j,a[s[i]-'a']);
if(i==j){
ans.push_back(i-anc+1);
anc=i+1;
}
}
for(auto it:ans){
cout<<it<<" ";
} cout<<endl;
}

return 0;

}
Leave a Comment