Optimal Partition String

February 25, 2024

Problem Statement: #

Given a string s, partition the string into as many parts as possible so that each letter appears in at most one part, and return the number of partitions you can create.

Example: #

• Input: s = "abacddbec"
• Output: 4
• Explanation: One optimal partitioning is ["abac", "dd", "b", "ec"]. Here, each letter appears in at most one part. Thus, the maximum number of partitions is 4.

Solution Approach: #

The problem can be solved by first scanning the string to determine the last occurrence of each character. Then, iterate through the string and use a greedy approach to partition the string whenever the current character’s last occurrence is reached. This ensures each character only appears in one part.

Algorithm Steps: #

1. Create a map to store the last occurrence index of each character in the string.
2. Iterate through the string, tracking the current partition’s start index and the farthest last occurrence index (maxLastOccurrence) seen so far for any character in the current partition.
3. If the current index matches the maxLastOccurrence, a partition is complete. Increase the partition count and update the start index for the next partition.
4. Continue until the entire string is partitioned.
5. Return the count of partitions.

Code: #

def optimalPartitionString(s):
    # Step 1: Map each character to its last occurrence in the string.
    lastOccurrence = {char: idx for idx, char in enumerate(s)}
    
    partitions = 0
    start = 0
    maxLastOccurrence = 0
    
    # Step 2: Iterate through the string to partition.
    for i, char in enumerate(s):
        maxLastOccurrence = max(maxLastOccurrence, lastOccurrence[char])
        
        # Step 3: If current index is the maxLastOccurrence, partition is complete.
        if i == maxLastOccurrence:
            partitions += 1
            start = i + 1  # Update start for the next partition.
            
    return partitions

# Example usage
s = "abacddbec"
print(optimalPartitionString(s))

Time Complexity: #

• O(N): Where N is the length of the string. The string is iterated over twice (once for creating the map of last occurrences and once for partitioning), leading to a linear time complexity.

Space Complexity: #

• O(1): The space complexity is constant (ignoring the input), as the map stores a fixed number of characters (at most 26 for English letters). The space used by the map does not grow with the size of the input string.