763. Partition Labels
Problem Description
The problem presents us with a string s
. Our goal is to partition s
into the maximum number of parts such that no letter appears in more than one part. This means that once a letter appears in a part, it cannot appear in any other part. After partitioning, when we concatenate all parts back together in the original order, the string should remain unchanged; it should be s
.
The resulting output should be a list of integers, where each integer represents the length of one of these partitions.
Intuition
The intuition behind this solution is to first understand that a partition can only end when all instances of a particular character included in the partition have been encountered. The last occurrence of each character defines the maximum possible extent of a partition.
To solve the problem, we track the last occurrence of each character using a dictionary. The keys are the characters from the string s
and the values are the indices of their last occurrences.
As we iterate over the string s
:
-
We continually update a
mx
variable to keep track of the farthest index that we must reach before we can end a partition. This is updated by looking at the last occurrence of the current character. -
When the current index
i
matchesmx
, it means we've included all occurrences of the characters seen so far in the current partition. At this point, we can end the current partition and start a new one. -
We append the size of the current partition to the answer list. The size is calculated as the difference between the current index
i
and the start index of the partitionj
, plus one. -
We then set the start of the next partition to be one index after the current index
i
.
In the end, we get a list of partition sizes that fulfill the requirements.
Learn more about Greedy and Two Pointers patterns.
Solution Approach
The solution uses a two-pass approach and utilizes a dictionary data structure to hold the last occurrence of each character in the string s
.
-
Building a dictionary of last occurrences: The first pass is over the string
s
. As we iterate, we capture the last position or index of every unique character in the dictionary calledlast
. This is constructed in the linelast = {c: i for i, c in enumerate(s)}
, making use of a dictionary comprehension. -
Partitioning based on last occurrences: The next part of the solution is where the actual partitioning logic is implemented:
- We initialize three variables:
mx
,j
, andans
. Themx
variable represents the furthest point a partition can reach before being cut. Thej
variable is the start index of the current partition, andans
is the list that will hold the sizes of the partitions. - We then iterate through the string
s
again, index by index, alongside the corresponding characters.- For each character at index
i
, we updatemx
to be the maximum value between the currentmx
and the last occurrence of the characterc
, like this:mx = max(mx, last[c])
. - If the current index
i
equalsmx
, it means all characters in the current partition will not appear again in the following parts of the string. This is the right place to 'cut' this partition.- We calculate the size of the current partition by subtracting the start index
j
of this partition from the current indexi
and adding 1 (i - j + 1
). This value is appended to theans
list. - Once we add the partition size to
ans
, we set the startj
of the next partition toi + 1
.
- We calculate the size of the current partition by subtracting the start index
- For each character at index
- We initialize three variables:
-
Output the result: After the iteration completes, we return the list
ans
which contains the sizes of all partitions.
The factors that make this algorithm work are:
- The dictionary captures the essential boundaries for our partitions by marking the last appearance of each character within the string.
- The two-pass mechanism ensures that we never 'cut' a partition too early, which ensures that each letter only appears in one part.
- The greedy approach - always updating
mx
to extend the partition as far as possible and only finalizing a partition when absolutely necessary - ensures that we maximize the number of partitions.
By following through with this approach, the function partitionLabels
partitions the string optimally as per the problem statement.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example string s = "abac"
. We want to create partitions in such a way that no letters are repeated in any of the partitions and to maximize the number of partitions. The output should be a list of the lengths of these partitions.
-
Building a dictionary of last occurrences: The first pass over the string
s
will give us a dictionarylast
with the last position of every character.- For our example,
last
would be{'a': 2, 'b': 1, 'c': 3}
.
- For our example,
-
Partitioning based on last occurrences:
- We initialize
mx
to-1
,j
to0
, andans
to an empty list. - We then loop through the string
s
, with the indices and characters.- At index
0
, the character is'a'
. We updatemx
to be the maximum ofmx
and the last occurrence of'a'
(mx = max(-1, 2)
), somx
becomes2
. - At index
1
, the character is'b'
. We updatemx
to bemax(2, 1)
as the last occurrence of'b'
is at index1
. Since2
is greater,mx
remains2
. - At index
2
, the character is'a'
. Since we have already accounted for the last occurrence of'a'
, we don't need to updatemx
it is still the right end of our partition. - At index
2
wheni
is equal tomx
, we can 'cut' the partition here.- We append the size of this partition to
ans
, which isi - j + 1
or2 - 0 + 1
, so we append3
. - We also set
j
to the next indexi + 1
, which is3
, ready for the next potential partition.
- We append the size of this partition to
- For the last character at index
3
,'c'
, the last occurrence is at3
itself. We updatemx
to3
. - Given that
i
equalsmx
at the last character, we have the end of another partition.- The size of the partition is again calculated as
i - j + 1
, yielding3 - 3 + 1
, so we append1
toans
.
- The size of the partition is again calculated as
- At index
- We initialize
-
Output the result: After the iteration completes,
ans
contains the sizes[3, 1]
, denoting the lengths of the partitionsaba
andc
. Hence, the final output is[3, 1]
.
By following the steps above, the input string abac
has been partitioned into ["aba", "c"]
, maximizing the number of parts and ensuring no letter appears in more than one part. The lengths of the partitions are [3, 1]
as per the expected output.
Solution Implementation
1class Solution:
2 def partitionLabels(self, S: str) -> List[int]:
3 # Create a dictionary to store the last occurrence of each character.
4 last_occurrence = {char: index for index, char in enumerate(S)}
5
6 # Initialize variables.
7 # `max_last` represents the farthest index any character in the current partition has been seen.
8 # `partition_start` represents the start of the current partition.
9 max_last = partition_start = 0
10
11 # This list will hold the sizes of the partitions.
12 partition_sizes = []
13
14 # Iterate through the characters of the string along with their indices.
15 for index, char in enumerate(S):
16 # Update `max_last` to be the max of itself and the last occurrence of the current character.
17 max_last = max(max_last, last_occurrence[char])
18
19 # If the current index is the last occurrence of all characters seen so far in this partition,
20 # that means we can end the partition here.
21 if max_last == index:
22 # Append the size of the current partition to the list (`index - partition_start + 1`).
23 partition_sizes.append(index - partition_start + 1)
24
25 # Update `partition_start` to the next index to start a new partition.
26 partition_start = index + 1
27
28 # Return the list of partition sizes.
29 return partition_sizes
30
1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5 public List<Integer> partitionLabels(String s) {
6 // Initialize an array to store the last appearance index of each character.
7 int[] lastIndices = new int[26]; // Assuming 'a' to 'z' only appear in the string.
8 int lengthOfString = s.length();
9 // Fill the array with the index of the last occurrence of each character.
10 for (int i = 0; i < lengthOfString; ++i) {
11 lastIndices[s.charAt(i) - 'a'] = i;
12 }
13
14 // Create a list to store the lengths of the partitions.
15 List<Integer> partitionLengths = new ArrayList<>();
16 int maxIndexSoFar = 0; // To keep track of the farthest reach of the characters seen so far.
17 int partitionStart = 0; // The index where the current partition starts.
18
19 // Iterate through the characters in the string.
20 for (int i = 0; i < lengthOfString; ++i) {
21 // Update the maxIndexSoFar with the farthest last occurrence of the current character.
22 maxIndexSoFar = Math.max(maxIndexSoFar, lastIndices[s.charAt(i) - 'a']);
23
24 // If the current index matches the maxIndexSoFar, we've reached the end of a partition.
25 if (maxIndexSoFar == i) {
26 // Add the size of the partition to the list.
27 partitionLengths.add(i - partitionStart + 1);
28 // Update the start index for the next partition.
29 partitionStart = i + 1;
30 }
31 }
32
33 // Return the list containing the sizes of the partitions.
34 return partitionLengths;
35 }
36}
37
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 // This function partitions the string such that each letter appears in at
8 // most one part, and returns a vector of integers representing the size of these parts.
9 vector<int> partitionLabels(string S) {
10 int lastIndex[26] = {0}; // Array to store the last index of each letter
11 int length = S.size(); // Get the size of the string
12
13 // Fill the array with the last index of each letter in the string
14 for (int i = 0; i < length; ++i) {
15 lastIndex[S[i] - 'a'] = i;
16 }
17
18 vector<int> partitions; // This will store the sizes of the partitions
19 int maxIndex = 0; // Maximum index of a character within the current partition
20 int anchor = 0; // Starting index of the current partition
21
22 for (int i = 0; i < length; ++i) {
23 maxIndex = max(maxIndex, lastIndex[S[i] - 'a']); // Update maxIndex for the current partition
24
25 // If the current index is the max index of the partition, it means we can make a cut here
26 if (maxIndex == i) {
27 partitions.push_back(i - anchor + 1); // Partition size is added to the result
28 anchor = i + 1; // Update the starting index of the next partition
29 }
30 }
31
32 return partitions; // Return the sizes of the partitions
33 }
34};
35
1function partitionLabels(inputString: string): number[] {
2 // Initialize an array to hold the last index at which each letter appears.
3 const lastIndex: number[] = Array(26).fill(0);
4 // Helper function to convert a character to its relative position in the alphabet.
5 const getCharacterIndex = (char: string) => char.charCodeAt(0) - 'a'.charCodeAt(0);
6 // Get the length of the input string.
7 const inputLength = inputString.length;
8
9 // Update the lastIndex array with the last position for each letter in the input.
10 for (let i = 0; i < inputLength; ++i) {
11 lastIndex[getCharacterIndex(inputString[i])] = i;
12 }
13
14 // Prepare an array to hold the lengths of the partitions.
15 const partitionLengths: number[] = [];
16 // Initialize pointers for tracking the current partition.
17 let start = 0, end = 0, maxIndex = 0;
18
19 for (let i = 0; i < inputLength; ++i) {
20 // Update the maximum index for the current partition.
21 maxIndex = Math.max(maxIndex, lastIndex[getCharacterIndex(inputString[i])]);
22 // If the current position matches the maxIndex, a partition is complete.
23 if (maxIndex === i) {
24 // Add the size of the current partition to the array.
25 partitionLengths.push(i - start + 1);
26 // Move the start to the next position after the current partition.
27 start = i + 1;
28 }
29 }
30
31 // Return the array of partition sizes.
32 return partitionLengths;
33}
34
Time and Space Complexity
Time Complexity:
The time complexity for the provided code can be analyzed as follows:
- The first line within the
partitionLabels
function uses a dictionary comprehension to store the last appearance index of each character. This runs inO(n)
time, wheren
is the length of strings
, because it iterates through the entire string once. - The subsequent
for
loop also runs through the string once and performs a constant number of operations within the loop. Hence, the complexity of this part isO(n)
. - Overall, since both the creation of the dictionary and the for loop run in linear time relative to the size of the input
s
, and occur sequentially, the total time complexity of the function isO(n)
.
Space Complexity:
- The space complexity is influenced by the additional storage used:
- The
last
dictionary which stores the index of the last occurrence of each character has at mostO(min(n, 26))
space complexity because there are at most 26 letters in the alphabet. In the case wheren < 26
, the dictionary would have at mostn
elements. - The
ans
list where the sizes of the partitions are stored will have a space complexity ofO(n)
in the worst case, where each character is a partition on its own.
- The
- Since the
last
dictionary has a fixed upper limit due to a finite alphabet, it's typically consideredO(1)
space, particularly in the context of largen
. - However, the list
ans
depends on the size of the input and can take up toO(n)
space in the worst case scenario. - Therefore, the overall space complexity of the function is
O(n)
, reflecting the worst-case scenario where the output list could grow linearly with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we