We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition Labels

Number: 768

Difficulty: Medium

Paid? No

Companies: Amazon, InMobi, Microsoft, Meta, Yandex, LinkedIn, Google, Sprinklr

Problem Description

Given a string s, partition it into as many parts as possible such that each letter appears in at most one part. After partitioning, concatenating the parts should yield the original string. The goal is to return a list of integers where each integer represents the size of the corresponding partition.

Key Insights

  • Determine the last occurrence of every character in the string.
  • Use a greedy approach to extend the current partition until all characters within it do not appear later in the string.
  • When the current index reaches the furthest last occurrence for characters seen so far, a partition can be closed.
  • Repeat the process for the remaining section of the string.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string because we traverse the string twice. Space Complexity: O(1) (or O(26) to be precise) for storing the last occurrences of each character.

Solution

We first iterate through the string to store the last index at which each character appears. Then, we traverse the string while maintaining two pointers: one for the start of the current partition and one to track the furthest last occurrence (end) of any character seen so far. For each character, we update the end pointer to be the maximum of its current value and the last index of that character. When the current index equals the end pointer, it means that all characters in the current partition do not appear later. We then determine the size of this partition, add it to the result list, and move to the next partition. We repeat this until the entire string is processed.

Code Solutions

# Python Solution
class Solution:
    def partitionLabels(self, s: str) -> list:
        # Step 1: Record the last occurrence of each character.
        last_occurrence = {char: i for i, char in enumerate(s)}
        # List to store the sizes of partitions.
        partitions = []
        start, end = 0, 0
        
        # Step 2: Iterate over the string to form partitions.
        for i, char in enumerate(s):
            # Update the end index for the current partition.
            end = max(end, last_occurrence[char])
            # When we reach the end of the partition.
            if i == end:
                partitions.append(end - start + 1)
                start = i + 1  # Move start to the next index.
        
        return partitions
← Back to All Questions