Partition Labels - Java Solution

1. Introduction

This blog post focuses on solving the "Partition Labels" problem, a task involving string manipulation and greedy algorithms. The challenge is to partition a given string into the maximum number of parts such that each letter appears in at most one part, and the concatenation of these parts forms the original string.

Problem

Given a string s, the objective is to partition the string into as many parts as possible, ensuring that each letter appears in only one part. The function should return a list of integers representing the size of these parts.

2. Solution Steps

1. First, determine the last index of each character in the string.

2. Use a greedy approach to partition the string:

a. Initialize two pointers, start and end, to keep track of the current partition.

b. Iterate through the string, updating the end to the farthest last index of the characters found so far.

c. When the current index reaches end, a partition is completed. Add the partition size to the result and update start and end for the next partition.

3. Continue the process until the end of the string is reached.

4. Return the list of partition sizes.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class PartitionLabels {
    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        System.out.println(partitionLabels(s)); // Test the function
    }

    // Function to partition the string and return the sizes of each part
    public static List<Integer> partitionLabels(String s) {
        int[] lastIndexes = new int[26]; // Store the last index of each character
        for (int i = 0; i < s.length(); i++) {
            lastIndexes[s.charAt(i) - 'a'] = i;
        }

        List<Integer> partitions = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, lastIndexes[s.charAt(i) - 'a']);
            if (i == end) {
                partitions.add(i - start + 1);
                start = i + 1;
            }
        }

        return partitions;
    }
}

Output:

[9, 7, 8]

Explanation:

1. partitionLabels: This function computes the sizes of partitions for the given string s.

2. It first creates an array to store the last index of each character in the string.

3. The function then iterates through s, using a greedy approach to find partitions. For each character, it updates the end to the farthest index that any character in the current partition can reach.

4. When the current index matches end, a partition is complete, and its size is added to the list partitions.

5. The process continues until all characters are partitioned.

6. The approach ensures that each partition is as large as possible while keeping each character in only one partition.

7. The returned list partitions contains the sizes of these partitions, representing the solution to the problem.