763.Partition_Labels(Medium).md

763. Partition Labels (Medium)

Date and Time: Aug 18, 2024, 14:54 (EST)

Link: https://leetcode.com/problems/partition-labels/

Question:

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.

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 <= 500

• s consists of lowercase English letters.

Walk-through:

1. Hashmap to store each element's last index

2. Use maxEnd to keep track of the current farthest index of a letter. If along the path, we reach index i at maxEnd, means all the letters that are included in this partition will not have the farthest index over maxEnd. Hence we find one valid parition. Remember, we have to first update maxEnd before we compare if current index i == maxEnd.

Python Solution:

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # Loop over s with the farthest index for each letter
        # Maintain `maxEnd` to keep track of the farthest index of a letter
        # If index i == maxEnd, we find a valid parition, because no letter has farthest index over maxEnd
        # TC: O(n), n=len(s), SC: O(1)
        hashmap = {}    # {letter: farthest_index}
        l, maxEnd = 0, 0
        ans = []    # contains partition size
        # Update each letter farthest index
        for i in range(len(s)):
            hashmap[s[i]] = i
        for r in range(len(s)):
            maxEnd = max(maxEnd, hashmap[s[r]])
            # Found valid partition
            if r == maxEnd:
                ans.append(r-l+1)
                l = r + 1
        return ans

Time Complexity: $O(n)$, n is the length of s, loop over the whole s string twice.
Space Complexity: $O(1)$, because we only store 26 keys in the hashmap at most, which is constant complexity.