Partition Labels Leetcode Problem 763 [Python Solution]

Welcome back!

Today, we're going to tackle an interesting and somewhat unique problem: Partition Labels.

This problem can be found on LeetCode, under problem number 763. It falls under the category of Greedy problems and is often associated with companies like Facebook.

Problem Overview

Question: You are given a string s.

Your task is to partition the string into as many parts as possible so that each letter appears in at most one part.

The partition must ensure that, after concatenating all the parts in order, the resultant string should be s.

You need to return a list of integers representing the size of these parts.

Let's dive into an example to better understand this problem.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]

Explanation:

The partition for this input string would be as follows:
– "ababcbaca"
– "defegde"
– "hijhklij"

This partition ensures that each letter appears in at most one part.

If we attempted a different partition like "ababcbacadefegde", "hijhklij," it would be incorrect because it splits s into fewer parts.

Understanding Constraints

Before we dive into the solution, let's understand the constraints provided in the problem statement:

• 1 <= s.length <= 500: The length of the input string s can vary from 1 to 500.
• s consists of lowercase English letters: The input string only contains lowercase English letters.

Efficient Python Code Solution

Now, let's move on to the efficient Python solution to solve this problem.

def partitionLabels(self, S: str) -> List[int]:
    count = {}
    res = []
    i, length = 0, len(S)

    # Build a hashmap to store the last occurrence index of each character in the string
    for j in range(length):
        c = S[j]
        count[c] = j

    curLen = 0
    goal = 0

    # Iterate through the string
    while i < length:
        c = S[i]
        goal = max(goal, count[c])
        curLen += 1

        # If the goal is reached (end of the current partition), add the length to the result
        if goal == i:
            res.append(curLen)
            curLen = 0
        i += 1

    return res

This Python solution is efficient and adheres to the given constraints.

Let's break down how it works step by step.

1. Building a Hashmap

The first part of the code involves building a hashmap to store the last occurrence index of each character in the input string S.

This step ensures we know where each character's last occurrence is, which is crucial for determining partition boundaries.

2. Iterating through the String

Next, we iterate through the string, character by character.

We maintain two variables:

• curLen: This variable tracks the size of the current partition.

We initialize it to 0.
– goal: This variable represents the end of the current partition.

It is initially set to 0.

3. Updating the goal and curLen

As we iterate through the string, we update curLen for each character and check if the last occurrence index of the current character is greater than the current goal.

If it is, we update the goal to that index.

4. Detecting Partition Boundaries

The key part of this algorithm is detecting when a partition is complete.

We do this by checking if the goal is equal to the current index (i).

When they match, it means we've reached the end of the current partition.

We add the length of the partition to the result list and reset curLen to 0, indicating the start of a new partition.

5. Returning the Result

Finally, we return the result list, which contains the sizes of all the partitions.

This algorithm is efficient with a time complexity of O(n) because it only requires a single pass through the input string, and the space complexity is O(1) since the hashmap has a fixed size of 26 characters.

Reasoning Behind Our Approach

The reasoning behind this approach lies in efficiently keeping track of the last occurrence index of each character.

By using this information, we can determine when a partition is complete and add its size to the result list.

This approach ensures that each character appears in at most one part, as required by the problem.

Related Interview Questions By Company:

• Best Time To Buy And Sell Stock II LeetCode
• Number Of Longest Increasing Subsequence LeetCode
• Kth Smallest Element In A BST LeetCode

Related Interview Questions By Difficulty:

• Hand Of Straights LeetCode
• Partition Labels LeetCode
• Maximum Sum Circular Subarray LeetCode

Conclusion

In this blog post, we tackled the LeetCode problem Partition Labels (problem number 763) using an efficient Python solution.

We started by understanding the problem, its constraints, and the overall approach.

We then provided a step-by-step explanation of the Python code and the reasoning behind our approach.

I hope this guide has been helpful to you, especially if you're a beginner in problem-solving on platforms like LeetCode.

If you have any questions, suggestions, or comments, please feel free to share them below.

Happy coding!

Question Link