Dare2Solve
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.
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.
s
and populate the lastIdx
dictionary with the index of the last occurrence of each character.res
to store the lengths of the partitions, and two variables curLast
and accu
to track the current end of the partition and the starting index of the next partition, respectively.curLast
to be the maximum of its current value and the last occurrence of the current character.curLast
, it means the current partition ends here. Append the length of the partition to res
and update accu
to be the index of the next character.res
list will contain the lengths of all partitions.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.
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).
class Solution {
public:
std::vector<int> partitionLabels(std::string s) {
std::unordered_map<char, int> lastIdx;
for (int i = 0; i < s.length(); i++) {
lastIdx[s[i]] = i;
}
int curLast = 0, accu = 0;
std::vector<int> 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;
}
};
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
class Solution {
public List<Integer> partitionLabels(String s) {
Map<Character, Integer> lastIdx = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
lastIdx.put(s.charAt(i), i);
}
List<Integer> 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;
}
}
/**
* @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;
};