Optimal Partition Of String - Leetcode Solution

Problem Statement:

Given a string s, divide s into some number of partitions such that every letter appears in at most one partition. Return a list of integers representing the size of these partitions.

Example:

Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The optimal partition is "ababcbaca", "defegde", "hijhklij". This is because every letter appears in at most one partition.

Solution:

Treat the given string as an array of characters, and maintain a dictionary of all characters and their last occurrence in the string. Traverse through the string, and for each character encountered, put the index of its last occurrence in a variable, say 'last_index'. Check whether this index is greater than the current index of traversal (say i). If it is, set the value of 'last_index' as the index of that last occurrence of the character, Otherwise, just keep traversing.

For each character encountered, keep on updating the maximum value of this 'last_index' for all the characters found up to the current index i. When traversing the string, if the current index 'i' is equal to the maximum of last_index values for the characters found upto that index say 'j', then the optimal partition for the sub array s[j+1:i] should be formed. Append the length of this partition to the result list.

Once the traversal is over, return the result list of partition lengths.

Pseudo Code:

1. Initialize a dictionary to store the last occurrences of all the characters in given string s.
2. Initialize a variable 'last_index' to -1 and an empty list 'partition_lengths'.
3. Traverse through the string s, for each index i: a. Find the last_index of the character currently being traversed via the dictionary constructed in step 1. b. Update the dictionary with the current index i as its value. c. If the value of last_index is less than the current index, then continue. d. Else, get the maximum value of last_index values for all the characters found up to index i. e. If the current index i is equal to the maximum index of the last occurrences of all the letters upto that index say 'j', then append the length of the partition s[j+1:i] to the partition_lengths list.
4. Return the list partition_lengths.

Time Complexity: O(N), where N is the length of the input string.

Code Implementation:

def partitionLabels(s: str) -> List[int]:
    # initialize variables
    last_occurrence = {char: idx for idx, char in enumerate(s)}
    last_index, partition_start = -1, 0
    partition_lengths = []

    # traverse through the string s
    for i in range(len(s)):
        char = s[i]
        last_index = max(last_index, last_occurrence[char])
        if i == last_index:
            partition_lengths.append(i - partition_start + 1)
            partition_start = i + 1

    return partition_lengths

1