Partition Labels
MedPrompt
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. For example, the string "ababcc" can be partitioned into ["abab", "cc"], but partitions such as ["aba", "bcc"] or ["ab", "ab", "cc"] are invalid.
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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iteratively builds partitions without any pre-computation. For each potential partition, it determines its required boundary by finding the furthest last occurrence of any character within it. This process is repeated until the entire string is partitioned. The main drawback is the repeated work in finding last occurrences.
Algorithm
- Initialize an empty list
partitionsand astartindex to 0. - Loop while
startis less than the string lengthn:- Find the last occurrence of the character
s.charAt(start), let this bemaxReach. - Iterate with an index
ifromstartup to the currentmaxReach. - In the loop, update
maxReachwith the last occurrence ofs.charAt(i)if it's greater than the currentmaxReach. This is done by calling a function likes.lastIndexOf(). - After the loop,
maxReachmarks the end of the minimal valid partition. - Add the size of this partition (
maxReach - start + 1) to thepartitionslist. - Update
starttomaxReach + 1.
- Find the last occurrence of the character
- Return the
partitionslist.
Walkthrough
This method finds partitions one by one. It starts by considering the character at the current start index. It finds its last occurrence to define an initial partition boundary. Then, it iterates through all characters within this tentative partition, checking their last occurrences and extending the boundary if any character appears later in the string. This process continues until the partition boundary stabilizes, at which point a valid partition has been found.
The main inefficiency comes from repeatedly calling s.lastIndexOf() (or an equivalent manual search) for characters within the current potential partition. Since lastIndexOf scans a large part of the string and is called inside a loop that also iterates through the string, the overall complexity becomes quadratic.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> partitionLabels(String s) { List<Integer> partitions = new ArrayList<>(); int n = s.length(); int start = 0; while (start < n) { // Find the furthest reach for the character at the start of the potential partition. int maxReach = s.lastIndexOf(s.charAt(start)); // Iterate through the characters within the current partition range [start, maxReach] // and expand maxReach if any character extends further. for (int i = start + 1; i <= maxReach; i++) { maxReach = Math.max(maxReach, s.lastIndexOf(s.charAt(i))); } // Once the loop finishes, maxReach is the end of the current valid partition. int partitionSize = maxReach - start + 1; partitions.add(partitionSize); // Move to the start of the next partition. start = maxReach + 1; } return partitions; }}Complexity
Time
O(N^2), where N is the length of the string. The `lastIndexOf` method takes O(N) time, and it is called within a loop that iterates through the string, leading to a quadratic time complexity.
Space
O(1), excluding the space required for the output list. Only a few variables are needed to keep track of indices.
Trade-offs
Pros
Conceptually straightforward, directly implementing the definition of a valid partition.
Does not require extra space for pre-computation (besides the result list).
Cons
Inefficient due to repeated scanning of the string to find the last index of characters.
The time complexity is quadratic, which is slow for larger strings (though acceptable for the given constraints).
This is an efficient greedy approach that solves the problem in linear time. It involves two passes over the string. The first pass records the last occurrence index of each character. The second pass then iterates through the string, using the pre-computed last indices to greedily find the smallest possible valid partition at each step.
Algorithm
- First Pass (Preprocessing):
- Create an integer array
lastIndicesof size 26, initialized to 0. - Iterate through the input string
sfromi = 0ton-1. - For each character
s.charAt(i), store its indexiinlastIndices[s.charAt(i) - 'a'].
- Create an integer array
- Second Pass (Partitioning):
- Initialize an empty list
result,start = 0, andend = 0. - Iterate through the string
sfromi = 0ton-1. - In each iteration, update
endto be the maximum of its current value and the pre-computed last index ofs.charAt(i). - If the current index
iis equal toend:- A partition is found. Add its length (
end - start + 1) toresult. - Update
starttoi + 1to mark the beginning of the next partition.
- A partition is found. Add its length (
- Initialize an empty list
- Return the
resultlist.
Walkthrough
The core idea is that for a substring to be a valid partition, the last occurrence of every character within that substring must also be contained within that substring. To maximize the number of partitions, we should make each partition as small as possible.
This approach first pre-computes the last seen index for all 26 lowercase letters in a single pass. Then, in a second pass, it iterates through the string maintaining a start pointer for the current partition and an end pointer for the farthest reach of any character seen in the current partition. This end is updated greedily. When the iteration index i catches up to end, it signifies that we have found the smallest possible valid partition. We record its size and start looking for the next one.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> partitionLabels(String s) { if (s == null || s.length() == 0) { return new ArrayList<>(); } // 1. Preprocessing: Find the last occurrence of each character. // An array is used as a hash map since characters are lowercase English letters. int[] lastIndices = new int[26]; for (int i = 0; i < s.length(); i++) { lastIndices[s.charAt(i) - 'a'] = i; } List<Integer> result = new ArrayList<>(); int start = 0; int end = 0; // 2. Partitioning: Iterate through the string to find partition boundaries. for (int i = 0; i < s.length(); i++) { // Greedily extend the end of the current partition to the farthest last occurrence. end = Math.max(end, lastIndices[s.charAt(i) - 'a']); // If the current index reaches the end of the partition, // it means we've found a complete, minimal partition. if (i == end) { result.add(end - start + 1); // Start a new partition from the next character. start = i + 1; } } return result; }}Complexity
Time
O(N), where N is the length of the string. The first pass to compute last indices takes O(N). The second pass to find partitions also takes O(N). The total time is O(N) + O(N) = O(N).
Space
O(1). We use an array of size 26 to store the last indices, which is constant space. The space for the result list is not counted in the complexity analysis.
Trade-offs
Pros
Highly efficient with a linear time complexity.
The logic is elegant and easy to implement once the greedy strategy is understood.
Cons
Requires two passes over the input string.
Uses a small amount of extra space (O(1)) for the
lastIndicesarray.
Solutions
Solution
public class Solution { public IList < int > PartitionLabels(string s) { int[] last = new int[26]; int n = s.Length; for (int i = 0; i < n; i++) { last[s[i] - 'a'] = i; } IList < int > ans = new List < int > (); for (int i = 0, j = 0, mx = 0; i < n; ++i) { mx = Math.Max(mx, last[s[i] - 'a']); if (mx == i) { ans.Add(i - j + 1); j = i + 1; } } return ans; }}class Solution {public List<Integer> partitionLabels(String s) { int[] last = new int[26]; int n = s.length(); for (int i = 0; i < n; ++i) { last[s.charAt(i) - 'a'] = i; } List<Integer> ans = new ArrayList<>(); int mx = 0, j = 0; for (int i = 0; i < n; ++i) { mx = Math.max(mx, last[s.charAt(i) - 'a']); if (mx == i) { ans.add(i - j + 1); j = i + 1; } } return ans; }}/** * @param {string} s * @return {number[]} */ var partitionLabels = function ( s ) { const last = new Array ( 26 ). fill ( 0 ); const idx = c => c . charCodeAt () - ' a ' . charCodeAt (); const n = s . length ; for ( let i = 0 ; i < n ; ++ i ) { last [ idx ( s [ i ])] = i ; } const ans = []; for ( let i = 0 , j = 0 , mx = 0 ; i < n ; ++ i ) { mx = Math . max ( mx , last [ idx ( s [ i ])]); if ( mx === i ) { ans . push ( i - j + 1 ); j = i + 1 ; } } return ans ; };class Solution {public: vector<int> partitionLabels(string s) { int last[26] = {0}; int n = s.size(); for (int i = 0; i < n; ++i) { last[s[i] - 'a'] = i; } vector<int> ans; int mx = 0, j = 0; for (int i = 0; i < n; ++i) { mx = max(mx, last[s[i] - 'a']); if (mx == i) { ans.push_back(i - j + 1); j = i + 1; } } return ans; }};class Solution: def partitionLabels(self, s: str) -> List[int]: last = {c: i for i, c in enumerate(s)} mx = j = 0 ans = [] for i, c in enumerate(s): mx = max(mx, last[c]) if mx == i: ans . append(i - j + 1) j = i + 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.