Greedy: Partition characters

Problem Statement:

You are given a string with multiple characters repeating.

You need to partiton the string into many parts such that each letter appears only once in any part.

Example

Input: asdfadaasfhjklqwertypcv

Output: [8, 6, 9]

We can split the string into [asdfadaa] [sfhjkl] [qwertypcv]

We cannot split as “[asdfadaa] [sfhjklqwertypcv]” because it will split the string into less parts.

We need to split the sting into more parts.

Solution

For the solution, we need to first get the last index of each character to help us find the segment which have characters different from the other segment.

We take 2 pointers “maxIndex” and “lastIndex”.

Then we make a segment whenever “i” and “maxIndex” are same.

Example:

S = "ababcbacadefegdehijhklij"

char        last index of each character 
a 		->	8
b 		->	5
c 		->	7
d 		->	14 
e 		->	15
f 		->	11
g 		->	13
h 		->	19
i 		->	22
j 		->	23
k 		->	20
l 		->	21

Initially we start with 0 and go till index 8. Because “a” last index is 8.

In that “b” and “c” will be covered.

Now again we traverse the string, the next segment will be at 15.

Similarly we solve the problem.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>

using namespace std;

vector<int> partition_labels(string S) 
{
  unordered_map<char,int> map;

  vector<int> ans;
  
  if(S.size()==0)
   return ans;
  
  for(int i=0;i<S.size();i++)
      map[S[i]]=i;

  int maxindex=0;
  int lastindex=0;
  
  for(int i=0;i<S.size();i++)
  {
      maxindex=max(maxindex,map[S[i]]);
      if(i==maxindex)
      {
          ans.push_back(maxindex-lastindex+1);
          lastindex=i+1;
      }
  }
  return ans;
}


int main()
{
    string S = "ababcbacadefegdehijhklij";
    
    vector<int> a = partition_labels(S);
    cout<<"The partition is ";

    for(int i = 0; i < a.size(); i++) {
      cout<<a.at(i)<<" ";
    }

    cout<<endl;
    return 0;
}

Output:

The partition is 9 7 8