# Partition Labels LeetCode Solution

Difficulty Level Medium

## Problem Statement

Partition Labels LeetCode Solution – You are given a string `s`. 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`.

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

## Examples and Explanation

Example 1:

```Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
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.```

Example 2:

```Input: s = "eccbbbbdec"
Output: [10]
Explanation:
The given string can not partitioned further as the letters will be repeated if partitioned.```

## Algorithm

Let’s look at example 1, we can notice that if we are including ‘a’ in the first partition then we need to include all the ‘a’s appearing in the string. So, we will include the substring from the first index till the last index of occurrences of ‘a’. In the second partition, `"defegde"` , we notice that including substring from the first index of ‘d’ till the last index of ‘d’ will not suffice. This means that we need to include all the last indices of all letters appearing between the first and last indices of ‘d’ as well.

## Code

### C++ program for Partition Labels

```class Solution {
public:
vector<int> partitionLabels(string s) {
map<char,int> index;
for(int i=0; i<s.size(); i++) {
index[s[i]]=i;
}
vector<int>res;
int pivot=0;
int last_index=0;
for(int curr=0; curr<s.size(); curr++) {
last_index = max(last_index, index[s[curr]]);
if(curr == last_index) {
res.push_back(last_index-pivot+1);
pivot=curr+1;
}
}
return res;
}
};```

### Java program for Partition Labels

```class Solution {
public List<Integer> partitionLabels(String s) {
int[] index = new int[26];
for (int i = 0; i < s.length(); ++i)
index[s.charAt(i) - 'a'] = i;

List<Integer> res= new ArrayList();
int pivot=0;
int last_index=0;
for(int curr=0; curr <s.length(); curr++) {
last_index = Math.max(last_index, index[s.charAt(curr) - 'a']);
if(curr == last_index) {