A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and 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.
Note:
S will have length in range [1, 500].S will consist of lowercase English letters ('a' to 'z') only.
The description was taken from https://leetcode.com/problems/partition-labels/.
#O(N) Time, O(1) Spaceclass Solution(object): def partitionLabels(self, S): seen = {} output = [] left, right = 0, 0 for i, char in enumerate(S): seen[char] = i for i, char in enumerate(S): right = max(right, seen[char]) if i == right: output.append(right - left + 1) left = right + 1 return outputThe problem description states that we are wanting to split the partitions in a way so that each letter appears in at most one part. Knowing this, we are going to need to map characters to their index values to reference where they are located in the string.
From there, the initial thought may be to use two pointers to signify the partition window between the first and last occurrence of the first character within the window. Although that would satisfy the constraints for that specific character, there may be additional characters in between that occur later in the string again. To solve this, we will still use two pointers to act as the beginning and end of a partition, but we will need to continuously update the right pointer with the last occurrence of each character that we come across, not just the first one in the window. That way, once we iterate to a partition end, we can be sure that no character within that current partition will come later in the string because otherwise, we wouldn't have caught up to the right pointer.
We can solve this problem in two passes.
Within the first pass, we will map each character to its index.
Within the second pass, we will update the right pointer to the greatest index of each character we encounter before we arrive at it. If we do arrive at it at any point, we will output the distance between the pointers as to the partition size and move the left pointer to the next partition.
Once we have traversed the entire string a second time, we will have each partition labeled.
Let's start by initializing the hashmap that we will use to track the last seen index of each character and the output.
seen = {} output = []
Next, we will set our pointers at the beginning index of the string.
left, right = 0, 0
We'll make our initial pass to map the index of each character. This will overwrite any previous indices by default until we finish the traversal.
for i, char in enumerate(S): seen[char] = i
Now, we will make our last traversal through an enumeration. An enumeration is just a traversal through the values while keeping track of a pointer for us.
for i, char in enumerate(S):
At the beginning of each iteration, we will update the right pointer if the last seen occurrence of the current character is greater than where the right pointer currently is.
We can view this as updating the requirement of where the partition end should be.
In the first example, "ababcbacadefegdehijhklij", the right pointer is first set to the "a", where it will stay until we arrive at it. After that, however, we would set it to "d", but if we left it there and partitioned that label, we would have forgotten about the "e" that comes after the last instance of "d".
In a way, this calculation of setting the right pointer is us saying, "now we have to account for this character, now this one, etc.", if we arrive at the right pointer and didn't have to set it to a later index, we had no other characters to account for within a label and can partition it.
right = max(right, seen[char])
Once we catch up to the right pointer, we will calculate the distance between pointers and partition that as the label.
The right pointer minus the left calculates the distance between pointers, right minus left plus one includes the left pointer to count the characters.
After we partition the label, we will move the left pointer to the right of the current partition's end so that we can begin partitioning the next label.
if i == right: output.append(right - left + 1) left = right + 1
Once we have partitioned each label, we will return the output.
return output