
Description
The partitionLabels
function takes a string s
and partitions it into as many parts as possible so that each letter appears in at most one part. It returns a list of integers representing the size of these parts.
Intuition
To solve this problem, we need to keep track of the last occurrence of each character in the string. By knowing the last index of each character, we can ensure that a character does not appear outside of its partition.
Approach
- Create a dictionary to store the last occurrence of each character: Iterate through the string
s
and populate thelastIdx
dictionary with the index of the last occurrence of each character. - Initialize variables: Create a list
res
to store the lengths of the partitions, and two variablescurLast
andaccu
to track the current end of the partition and the starting index of the next partition, respectively. - Iterate through the string: For each character in the string, update
curLast
to be the maximum of its current value and the last occurrence of the current character. - Partition the string: When the current index equals
curLast
, it means the current partition ends here. Append the length of the partition tores
and updateaccu
to be the index of the next character. - Return the result: The
res
list will contain the lengths of all partitions.
Complexity
Time Complexity:
O(n), where n is the length of the string. We iterate through the string twice: once to create the lastIdx
dictionary and once to partition the string.
Space Complexity:
O(1) for the res
list and lastIdx
dictionary, as the size of the dictionary is bounded by the number of unique characters (which is constant, 26 in the case of lowercase English letters).
Code
C++
class Solution {
public:
std::vector partitionLabels(std::string s) {
std::unordered_map lastIdx;
for (int i = 0; i < s.length(); i++) {
lastIdx[s[i]] = i;
}
int curLast = 0, accu = 0;
std::vector res;
for (int i = 0; i < s.length(); i++) {
curLast = std::max(curLast, lastIdx[s[i]]);
if (i == curLast) {
res.push_back(i + 1 - accu);
accu = i + 1;
}
}
return res;
}
};
Python
class Solution:
def partitionLabels(self, s: str) -> List[int]:
lastIdx = {char: idx for idx, char in enumerate(s)}
res = []
curLast, accu = 0, 0
for i, char in enumerate(s):
curLast = max(curLast, lastIdx[char])
if i == curLast:
res.append(i + 1 - accu)
accu = i + 1
return res
Java
class Solution {
public List partitionLabels(String s) {
Map lastIdx = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
lastIdx.put(s.charAt(i), i);
}
List res = new ArrayList<>();
int curLast = 0, accu = 0;
for (int i = 0; i < s.length(); i++) {
curLast = Math.max(curLast, lastIdx.get(s.charAt(i)));
if (i == curLast) {
res.add(i + 1 - accu);
accu = i + 1;
}
}
return res;
}
}
JavaScript
/**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function (s, lastIdx = {}) {
for (let i = 0; i < s.length; i++) {
lastIdx[s[i]] = i;
}
let curLast = 0, res = [], accu = 0;
for (let i = 0; i < s.length; i++) {
curLast = Math.max(curLast, lastIdx[s[i]]);
if (i === curLast) {
res.push(i + 1 - accu);
accu = i + 1;
}
}
return res;
};