Partition Labels - Python Solution

1. Introduction

"Partition Labels" is a problem that involves string manipulation and interval merging. The challenge is to partition a string into the smallest number of substrings such that each letter appears in at most one part. This problem tests one's ability to analyze character frequencies and intervals in a string.

Problem

Given a string s, the goal is to partition the string into as many parts as possible so that each letter appears in at most one part. After concatenating all the parts in order, the resultant string should be s. The task is to return a list of integers representing the size of these parts.

2. Solution Steps

1. First, find the last occurrence of each character in the string.

2. Initialize variables to keep track of the start and end of the current partition.

3. Iterate through the string and for each character, update the end of the current partition to the furthest last occurrence of any character in the current partition.

4. When the end of the partition is reached (matches the current index), finalize the partition size and start a new partition.

5. Continue this process for the entire string.

6. Add the size of each finalized partition to the result list.

3. Code Program

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    start = end = 0
    result = []

    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            result.append(end - start + 1)
            start = i + 1

    return result

# Example Usage
print(partitionLabels("ababcbacadefegdehijhklij"))
print(partitionLabels("eccbbbbdec"))

Output:

[9, 7, 8]
[10]

Explanation:

1. Last Occurrence Mapping: A dictionary last is created mapping each character to its last occurrence in the string.

2. Partition Tracking: Variables start and end track the beginning and end of the current partition.

3. Iterative Partitioning: The string is iterated through, extending the end of the partition to the furthest last occurrence of any character in it.

4. Finalizing Partitions: When the current index reaches the end, the partition is finalized and its size is added to result.

5. Result Compilation: The result list accumulates the sizes of all partitions.

6. Complete Partitioning: The process ensures each character appears in only one partition, and the concatenation of all partitions is the original string.