Introduction

In this blog post, we will explore how to solve the LeetCode problem "763" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. For example, the string "ababcc" can be partitioned into ["abab", "cc"], but partitions such as ["aba", "bcc"] or ["ab", "ab", "cc"] are invalid. 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.

Explanation

Here's a breakdown of the approach and the Python code:

• Find Last Occurrences: The key idea is to first determine the last occurrence of each character in the string. This allows us to know the maximum possible extent of a partition containing that character.
• Greedy Partitioning: Iterate through the string, maintaining the end of the current partition. Expand the partition's end as necessary based on the last occurrences of characters encountered within the current partition.

• Record Partition Sizes: When the current index reaches the end of the current partition, record the size of the partition and start a new one.

• Runtime & Storage Complexity: O(N) runtime, O(1) storage (specifically, O(26) which simplifies to O(1) because the alphabet size is constant).

Code

    def partitionLabels(s: str) -> list[int]:
    """
    Partitions a string into as many parts as possible so that each letter appears in at most one part.

    Args:
        s: The input string.

    Returns:
        A list of integers representing the size of these parts.
    """

    last_occurrence = {}
    for i, char in enumerate(s):
        last_occurrence[char] = i

    partitions = []
    start = 0
    end = 0
    for i, char in enumerate(s):
        end = max(end, last_occurrence[char])  # Extend partition if necessary
        if i == end:
            partitions.append(end - start + 1)
            start = i + 1

    return partitions