Partition Labels

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
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.


  • S will have length in range [1, 500].
  • S will consist of lowercase English letters ('a' to 'z') only.



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

public class PartitionLabels {

    public static List<Integer> partitionLabels(String S) {
        List<Character> values = new ArrayList<>();

        for (int i=0; i< S.length(); i++) {
            if (!values.contains(S.charAt(i))) {

        List<String> partitions = new ArrayList<>();
        int partitionBegin = S.indexOf(values.get(0));
        int partitionEnd = S.lastIndexOf(values.get(0));

        for(int i=1; i< values.size(); i++) {
            int startIndex = S.indexOf(values.get(i));
            int endIndex = S.lastIndexOf(values.get(i));
            if ((startIndex> partitionEnd)) {
                partitions.add(S.substring(partitionBegin, partitionEnd + 1));
                partitionBegin = startIndex;
                partitionEnd = endIndex;
            } else if (endIndex > partitionEnd) {
                partitionEnd = endIndex;
        partitions.add(S.substring(partitionBegin, partitionEnd + 1)); -> System.out.print(x + " " ));
        return -> x.length()).collect(Collectors.toList());

    public static void main(String[] args) {
        List<Integer> values = partitionLabels("ababcbacadefegdehijhklij"); -> System.out.print(x + " " ));

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s