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]
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.

Note:

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

Solution:

Logic:

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

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))) {
                values.add(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));
        partitions.stream().forEach(x -> System.out.print(x + " " ));
        return partitions.stream().map(x -> x.length()).collect(Collectors.toList());
    }

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