# 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: #

- Create a map to store the last occurrence index of each character in the string.
- 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. - If the current index matches the
`maxLastOccurrence`

, a partition is complete. Increase the partition count and update the start index for the next partition. - Continue until the entire string is partitioned.
- 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.