Leetcode #763 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.

Input s = “ababcbacadefegdehijhklij”;

Output = [9, 7, 8]

The parts are : “ababcbaca”, “defegde”, “hijhklij”.

To solve this problem, we need to find the last index of every character. For example, the last index of ‘a’ is 8. We store those values in a map. When we traverse through the string, as soon as we arrive at the maximum index possible for a given substring, we add that length to the list.

public List<Integer> partitionLabels(String S) {
        Map<Character, Integer> map = new HashMap<>();
        // Store the last index of every character
        for(int i = 0; i < S.length(); i++) {
            char ch = S.charAt(i);
            map.put(ch, i);
        }
        int max = 0;
        List<Integer> result = new ArrayList<>();
        int start = 0;
        for(int i = 0; i < S.length(); i++) {
            char ch = S.charAt(i);
            int index = map.get(ch);
            max = Math.max(index, max);
            // we evaluate the maximum possible index of the current         substring
            if(max == i) {
                int len = max - start + 1;
                result.add(len);
                start = i + 1;
            }
        }
        return result;
    }

Time complexity of the solution = O(n), where n is the total number of elements.