763. Partition-Labels

The intuition here is that we should keep track of where the last index of each letter is. When we consider each partition, we need to end the partition on the last index of the characters inside the current partition. For example, if we have a partition that contains the letter a, we need to end the partition at the last index of a and we need to consider this for all characters within the partition. We can keep track of the last index of each character in a dictionary. Then we can iterate through the string and keep track of the last index of the current partition. If we reach the last index of the current partition, we can add the length of the partition to the result and start a new partition.

Some things to note:

• we know that s consists of lowercase english letters (26 characters in total) - therefore we can store the last index in constant space

When we find a partition, we can append it to the result list and return it once we are done.

Edge cases to consider:

• I initially forgot to add the last partition to the result array because I’m goofy like that (it was a one line fix so its aite)

class Solution(object):
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        count = 26
        last_index = [-1] * 26
        for i in range(len(s) - 1, -1, -1):
            index = ord(s[i]) - ord('a')
            if last_index[index] == -1:
                last_index[index] = i
                count -= 1

            if count == 0:
                break

        res = []
        curr_start = 0
        curr_end = 0
        for i in range(len(s)):
            if i > curr_end:
                res.append(curr_end - curr_start + 1)
                curr_start = i
            index = ord(s[i]) - ord('a')
            curr_end = max(curr_end, last_index[index])
        res.append(curr_end - curr_start + 1)

        return res

Time Complexity : O(n)

Space Complexity : O(1)

• since we know that alphabet consists of 26 letters