Partition Labels
Partition Labels: Splitting Strings into Substrings
The Partition Labels problem involves dividing a string into substrings so that each character appears in at most one substring.
This problem highlights the efficient use of intervals and string manipulation. In this article, we’ll break down the problem, understand its logic, and implement a solution.
Problem Description
You are given a string s consisting of lowercase english letters.
We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.
Return a list of integers representing the size of these substrings in the order they appear in the string.
Explanation: The string can be split into [“xyxxy”, “zbzbb”, “i”, “s”, “l”].
Constraints: 1 <= s.length <= 100
Approach
Key Insights
Last Occurrence of Characters
- To determine the range of a substring, identify the last occurrence of each character in the string.
Merging Ranges
- Use the last occurrences to determine where each substring should end.
- If a character within a substring extends beyond the current range, expand the range accordingly.
Breaking into Substrings
- Split the string at the end of each range.
Algorithm
Track Last Occurrences:
- Use a dictionary to map each character to its last occurrence in the string.
Iterate Through the String:
- Use two pointers:
startto track the beginning of the current substring.endto track the farthest point of the current substring.
- Use two pointers:
Form Substrings:
- When the current index matches the
end, a substring ends. Add its size to the result list and updatestartto the next index.
- When the current index matches the
There is only one approach to solve this problem –
- Two Pointers (Greedy)
1. Two Pointers (Greedy)
- Time complexity: O(n)
- Space complexity: O(m)
class Solution:
def partitionLabels(self, s: str) -> List[int]:
lastIndex = {}
for i, c in enumerate(s):
lastIndex[c] = i
res = []
size = end = 0
for i, c in enumerate(s):
size += 1
end = max(end, lastIndex[c])
if i == end:
res.append(size)
size = 0
return resclass Solution {
public:
vector partitionLabels(string s) {
unordered_map lastIndex;
for (int i = 0; i < s.size(); i++) {
lastIndex[s[i]] = i;
}
vector res;
int size = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
size++;
end = max(end, lastIndex[s[i]]);
if (i == end) {
res.push_back(size);
size = 0;
}
}
return res;
}
}; public 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 res = new ArrayList<>();
int size = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
size++;
end = Math.max(end, lastIndex.get(s.charAt(i)));
if (i == end) {
res.add(size);
size = 0;
}
}
return res;
}
} class Solution {
/**
* @param {string} S
* @return {number[]}
*/
partitionLabels(S) {
let lastIndex = {};
for (let i = 0; i < S.length; i++) {
lastIndex[S[i]] = i;
}
let res = [];
let size = 0, end = 0;
for (let i = 0; i < S.length; i++) {
size++;
end = Math.max(end, lastIndex[S[i]]);
if (i === end) {
res.push(size);
size = 0;
}
}
return res;
}
}
