Leetcode Problem: Partition Labels
Two Pointer JavaScript Solution Walkthrough
I’ve been gaining confidence in my algorithm solving skills. So much so that I’ve graduated to the medium difficulty Leetcode problems. Yay! Can I effortlessly solve every problem I see? Hell no! I'm at the stage where given the problem I can normally come up with a working brute force solution. However, when it comes to finding the most optimized answer, I usually look for a few hints. But that's ok! As long as I spend time fully understanding the solution before I move on, I will have learned a new trick or two and can apply them to the next problem.
The following is one such problem:
Partition Labels Problem
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.
Note:
Swill have a length in the range[1, 500].Swill consist of lowercase English letters ('a'to'z') only.
Example:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation: The partition is "ababcbaca", "defegde", "hijhklij".Algorithm
To solve the problem, we will use a two pointer solution. See steps below:
Steps:
- First we create a hashmap of the last index of each unique character in the string. This is done by looping through the string and storing the index at which each letter occurs. If a letter is repeated, the hash will update with the greater index and only the last occurrence will be saved.
- Next comes the two pointer part. First we will initialize our partitions array (this is what we will be returning) and we initialize our two pointers to the start of the string (set end and start to 0).
- Then we loop through the string, setting the end pointer. The end pointer is the bigger value between the index we are on, and the last index of the character we are on (use the hashmap!).
- Next we compare the position of our end pointer against where we are in terms of iterating over the string. If the current index is not the same as the end index, we have to keep moving and do nothing.
- However, if the end and current index are the same then we must be at the end of a partition. Basically, this character wont appear again so you should make a cut in the string to ensure we get the maximum number of partitions.
- To make a cut, push the length of the segment into the partitions array. Then we update our start pointer to one after the end of the last partition.
- After the end of the loop, we simply return the partitions array.
Solution Code
var partitionLabels = function(S) { let lastIndex = {} for (let i = 0; i < S.length; i++){
lastIndex[S[i]]= i
} let partitions = []
let start = 0
let end = 0 for (let i = 0; i < S.length; i++) {
end = Math.max(end, lastIndex[S[i]])
if (i === end) {
partitions.push(i — start + 1)
start = i + 1
}
} return partitions
}
Space-Time Complexity
Never move on from a problem until you complete the space-time complexity analysis. It can help trigger a signal to a brute force solution where a more optimized approach may exist.
For the solution code above:
Space Complexity: O(n) This has to do with the step where we store the last index of each character. In theory, you could have each character be unique, resulting in O(n) space needed for that hash.
Time Complexity: O(n) We loop through the array twice. Once to create the hash of the last indices and again to create the partitions. This results in a time complexity of 2*O(n) at the worst case. But we don't care about coefficients and therefore we drop the 2 at the beginning.
More (Medium) Problems
After completing an algorithm, especially one where I needed some extra help, I like to solve another similar problem. There's nothing wrong with looking at solutions, but to make sure you are learning try to apply the skills to a new problem.
Here’s a related Leetcode suggested problem: Merge Intervals. Give it a try!
