Partition Labels

A string s of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts

Example:

Input:  str="ababcbacadefegdehijhklij"
Output: arr[]={9,7,8}

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PartitionLabels {
    public static void main(String[] args) {
        String S = "ababcbacadefegdehijhklij";
        List<Integer> part = partitionLabels(S);
        System.out.println(Arrays.asList(part));
    }

    // function to partition the string
    private static List<Integer> partitionLabels(String S) {
        int f[] = new int[26];
        List<Integer> res = new ArrayList<Integer>();
        if (S.length() == 0)
            return res;
        for (int i = 0; i < S.length(); i++)
            f[S.charAt(i) - 'a'] = i;

        int x = 0, y = 0;
        for (int i = 0; i < S.length(); i++) {
            x = Math.max(x, f[S.charAt(i) - 'a']);
            if (i == x) {
                res.add(i - y + 1);
                y = i + 1;
            }

        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to partition the string
vector<int> partitionLabels(string S) 
{
       int f[26]={0};
         vector<int> res;
        if(S.size()==0)
               return res;
        for(int i=0;i<S.size();i++) 
               f[S[i]-'a']=i;
       
        int x=0,y=0;
        for(int i=0;i<S.size();i++)
        {
            x=max(x,f[S[i]-'a']);
            if(i==x)
            {
                  res.push_back(i-y+1);
                  y=i+1;
            }
                   
        }
      return res;
}
int main()
{
    string S = "ababcbacadefegdehijhklij";
    vector<int> part=partitionLabels(S);
    for(int i=0;i<part.size();i++)
       cout<<part[i]<<" ";
    return  0;
}