763. Partition Labels

/**

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

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

 */

See solution to the problem on github here : https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/PartitionLabels.java

This is an interesting problem that repeats often.

Algorithm is:

  1. Find last index of each character
  2. Create a variable last index which stores the last index of characters so far seen – ‘lastOccur’ in code below.
  3. Iterate the string from left to right, check last index of the current character and if larger than the lastOccur character set lastOccur to the last index of current character.
  4. If current index is same as lastOccur – I,e you have reached the block in string that represents last index of characters so far seen then you have found a partition.
    1. When new partition is found, update the sentinel value ‘lastEnd’ which you can use as beginning index for the next partition.

Here is the code:

public List<Integer> partitionLabels(String str) {
    int [] index = new int[26];
    for (int i =0; i < str.length(); i++) {
        index[str.charAt(i)-'a'] = i; //creating a map that has last character index is key....
    }
    List<Integer> out = new ArrayList<>();
    int lastOccur = 0;
    int lastEnd = 0;
    for (int i=0; i < str.length(); i++) {
        lastOccur = Math.max(lastOccur, index[str.charAt(i)-'a']);
        if (i==lastOccur) {
            out.add(i+1-lastEnd);
            lastEnd = i + 1;
        }
    }
    return out;
}