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 <= 500sconsists 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;
}
};
Input
Output
#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) {
partitionIndices.add(i - prevIdx + 1);
prevIdx = i + 1;
}
}
return partitionIndices;
}
}
Input
Output
#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
}
Input
Output
#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
Input
Output
#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)
{
result.Add(i - start + 1);
start = lastMax + 1;
}
}
return result;
}
}
}
Input
Output