## Algorithm

Problem Name: 763. Partition Labels

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.

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]
```

Constraints:

• `1 <= s.length <= 500`
• `s` consists of lowercase English letters.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
// Straightforward two pointers:
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int>res;
int maxPos = 0, pre = -1;
for(int i = 0; i  <  S.size(); i++){
for(int j = maxPos + 1; j  <  S.size(); j++)
if(S[j] == S[i]) maxPos = max(maxPos, j);
if(i == maxPos){
res.push_back(i - pre);
pre = i;
}
}
return res;
}
};

// O(N)
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int>res;
vector<int>pos(26);
for(int i = 0; i < S.size(); i++) pos[S[i] - 'a'] = i;
int maxPos = 0, pre = -1;
for(int i = 0; i  <  S.size(); i++){
maxPos = max(maxPos, pos[S[i] - 'a']);
if(i == maxPos){
res.push_back(i - pre>;
pre = i;
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd

Output

cmd
[9,7,8]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List partitionLabels(String s) {
Map lastIndex = new HashMap<>();
for (int i = 0; i  <  s.length(); i++) {
lastIndex.put(s.charAt(i), i);
}
List < Integer> partitionIndices = new ArrayList<>();
int currMaxIdx = -1;
int prevIdx = 0;
for (int i = 0; i  <  s.length(); i++) {
currMaxIdx = Math.max(currMaxIdx, lastIndex.get(s.charAt(i)));
if (i == currMaxIdx) {
prevIdx = i + 1;
}
}
return partitionIndices;
}
}
``````
Copy The Code &

Input

cmd

Output

cmd
[9,7,8]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const partitionLabels = function (S) {
if (S == null || S.length === 0) {
return null
}
const list = []
// record the last index of the each char
const map = new Array(26).fill(0)
const a = 'a'.charCodeAt(0)
for (let i = 0, len = S.length; i  <  len; i++) {
map[S.charCodeAt(i) - a] = i
}
// record the end index of the current sub string
let last = 0
let start = 0
for (let i = 0, len = S.length; i  <  len; i++) {
last = Math.max(last, map[S.charCodeAt(i) - a])
if (last === i) {
list.push(last - start + 1)
start = last + 1
}
}
return list
}
``````
Copy The Code &

Input

cmd
s = "eccbbbbdec"

Output

cmd
[10]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
sizes = []
while S:
i = 1
while set(S[:i]) & set(S[i:]):
i += 1
sizes.append(i)
S = S[i:]
return sizes
``````
Copy The Code &

Input

cmd
s = "eccbbbbdec"

Output

cmd
[10]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0763_PartitionLabels
{
public IList < int> PartitionLabels(string S)
{
int[] last = new int[26];
for (int i = 0; i  <  S.Length; i++)
last[S[i] - 'a'] = i;

int start = 0, lastMax = 0;
var result = new List < int>();
for (int i = 0; i  <  S.Length; i++)
{
lastMax = Math.Max(lastMax, last[S[i] - 'a']);
if (i == lastMax)
{
start = lastMax + 1;
}
}
return result;
}
}
}
``````
Copy The Code &

Input

cmd