# Optimal Partition of String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/optimal-partition-of-string)
Canonical: https://scaleengineer.com/dsa/problems/optimal-partition-of-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Hash Table, String
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign)
---
## Problem
Given a string `s`, partition the string into one or more **substrings** such that the characters in each substring are **unique**. That is, no letter appears in a single substring more than **once**.

Return _the **minimum** number of substrings in such a partition._

Note that each character should belong to exactly one substring in a partition.

**Example 1:**

**Input:** s = "abacaba"
**Output:** 4
**Explanation:**
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

**Example 2:**

**Input:** s = "ssssss"
**Output:** 6
**Explanation:**
The only valid partition is ("s","s","s","s","s","s").

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of only English lowercase letters.

# Approaches
## Naive Greedy Approach with Nested Loops
This approach uses a straightforward greedy strategy with a naive implementation for checking duplicates. The core idea is to extend the current substring as much as possible. We iterate through the string, and for each character, we check if it has already appeared in the current substring. The check is done by a nested loop that scans from the beginning of the current substring to the current position. If a duplicate is found, we end the current substring, start a new one, and increment our partition count.
**Time:** O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop can run up to N times in the worst case (e.g., a string with no repeating characters), leading to a quadratic time complexity. · **Space:** O(1), as we only use a few integer variables to keep track of state (partition count and start index).
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1).
**Cons:** The time complexity of O(N^2) is inefficient and will likely result in a 'Time Limit Exceeded' error for larger inputs as specified in the constraints (N up to 10^5).
### Explanation
The algorithm maintains a pointer, `startOfPartition`, which marks the beginning of the current substring being formed. It then iterates through the string with a main pointer `i`. For each character `s.charAt(i)`, it uses a second, inner loop to scan the slice `s.substring(startOfPartition, i)` to see if `s.charAt(i)` has appeared before. If a duplicate is encountered, a partition is made right before the current character. This means we increment the partition count and update `startOfPartition` to the current index `i`. This process continues until the entire string is traversed.

```java
class Solution {
    public int partitionString(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int partitions = 1;
        int startOfPartition = 0;
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            // Linearly scan the current partition for a duplicate
            for (int j = startOfPartition; j < i; j++) {
                if (s.charAt(j) == currentChar) {
                    // Duplicate found, start a new partition
                    partitions++;
                    startOfPartition = i;
                    break;
                }
            }
        }
        return partitions;
    }
}
```
### Algorithm
*   Initialize `partitions = 1` and `startOfPartition = 0`.
*   Iterate through the string `s` with an index `i` from `0` to `s.length() - 1`.
*   For each character `s.charAt(i)`, perform a linear scan on the current substring, from `startOfPartition` to `i-1`.
*   Use an inner loop with index `j` to check if `s.charAt(j) == s.charAt(i)`.
*   If a duplicate is found, it means the current character cannot be part of the current substring.
*   Increment `partitions`, and start a new substring by setting `startOfPartition = i`.
*   Break the inner loop and continue with the next character.
*   If no duplicate is found, the character is added to the current substring by simply advancing `i`.
*   After the loop finishes, return the total `partitions` count.

## Greedy Approach with HashSet
This approach improves upon the naive method by optimizing the duplicate-checking process. It still employs the same greedy strategy of making each substring as long as possible, but instead of a linear scan, it uses a `HashSet`. A `HashSet` provides average O(1) time complexity for checking the existence of an element. We maintain a set of characters for the current substring. When we encounter a character that's already in the set, we start a new partition.
**Time:** O(N), where N is the length of the string. We perform a single pass through the string, and each operation on the `HashSet` (`add`, `contains`, `clear`) takes, on average, O(1) time. · **Space:** O(K), where K is the number of unique characters in the alphabet. Since the problem states the string consists of only lowercase English letters, K is at most 26. Therefore, the space complexity is constant, O(1).
**Pros:** Optimal time complexity of O(N).; Relatively easy to implement and understand.; Handles the problem constraints efficiently.
**Cons:** While efficient, it has a slightly higher constant factor overhead compared to array-based or bitmasking solutions due to the use of a general-purpose `HashSet` object and its hashing mechanism.
### Explanation
We iterate through the string once. A `HashSet` called `seen` keeps track of the unique characters in the substring we are currently building. For each character `c` from the input string, we check if it's in `seen`. If `seen.contains(c)` is true, it signifies the end of the current unique-character substring. We then increment our partition counter, clear the `seen` set completely, and add `c` to start the next substring. If `c` is not in `seen`, we simply add it and continue, extending the current substring.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int partitionString(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int partitions = 1;
        Set<Character> seen = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (seen.contains(c)) {
                partitions++;
                seen.clear();
                seen.add(c);
            } else {
                seen.add(c);
            }
        }
        return partitions;
    }
}
```
### Algorithm
*   Initialize `partitions = 1`. If the string is empty, return 0.
*   Create a `HashSet<Character>` named `seen` to store the characters of the current substring.
*   Iterate through the input string `s` character by character.
*   For each character `c`:
    *   Check if `c` is already present in the `seen` set using `seen.contains(c)`.
    *   If it is present, a new partition must be started. Increment `partitions`, clear the `seen` set, and then add `c` to the now-empty set.
    *   If it is not present, add `c` to the `seen` set to extend the current substring.
*   After iterating through all characters, return the final `partitions` count.

## Optimized Greedy Approach with Bitmasking
This is the most optimized greedy approach, leveraging the constraint that the string only contains lowercase English letters. Instead of a `HashSet` or an array, we can use a single integer as a bitmask to track the characters seen in the current substring. Since there are only 26 possible characters, we can map each character to one of the first 26 bits of an integer. This method is extremely fast as bitwise operations are very low-level and efficient.
**Time:** O(N), where N is the length of the string. We iterate through the string once, and all bitwise operations inside the loop are executed in constant time. · **Space:** O(1). The space required is constant as we only use a few integer variables, regardless of the input size.
**Pros:** Extremely fast with the best possible time complexity and very low constant factors.; Minimal space usage, requiring only a single integer for tracking.; Most efficient solution for the given constraints.
**Cons:** The logic might be slightly less intuitive for developers not comfortable with bitwise operations.; This approach is specifically tailored to a small, fixed character set and is less generalizable than a HashSet-based solution.
### Explanation
The algorithm uses an integer, `mask`, initialized to 0. As we iterate through the string, for each character `c`, we determine its corresponding bit. For example, 'a' maps to bit 0, 'b' to bit 1, and so on. We check if this bit is already set in our `mask` using the bitwise AND operator. If it is, we've found a duplicate, so we increment the partition count and reset the `mask` to contain only the bit for the current character. If the bit is not set, we set it using the bitwise OR operator, effectively adding the character to our current substring's set. This avoids the overhead of data structures like `HashSet` and is highly performant.

```java
class Solution {
    public int partitionString(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int partitions = 1;
        int mask = 0; // Use an integer as a bitmask
        for (char c : s.toCharArray()) {
            int bitPosition = c - 'a';
            int bit = 1 << bitPosition;
            
            // Check if the bit for the current character is already set
            if ((mask & bit) != 0) {
                // Duplicate found, start a new partition
                partitions++;
                // Reset the mask for the new partition
                mask = bit;
            } else {
                // No duplicate, add the character to the current partition's mask
                mask |= bit;
            }
        }
        return partitions;
    }
}
```
### Algorithm
*   Initialize `partitions = 1`. If the string is empty, return 0.
*   Initialize an integer `mask = 0`. This integer will serve as a bitmask.
*   Iterate through the input string `s` character by character.
*   For each character `c`:
    *   Calculate the bit position corresponding to the character (e.g., `c - 'a'`).
    *   Create a value `bit` representing this character's bit (e.g., `1 << (c - 'a')`).
    *   Use a bitwise AND (`&`) to check if the character's bit is already set in `mask`.
    *   If `(mask & bit) != 0`, the character is a duplicate in the current substring. Increment `partitions` and reset the `mask` to be just the current character's `bit`.
    *   If the bit is not set, use a bitwise OR (`|`) to set the bit in the `mask`: `mask |= bit`.
*   Return the final `partitions` count.

# Solutions
### Java

```java
class Solution {
public
  int partitionString(String s) {
    Set<Character> ss = new HashSet<>();
    int ans = 1;
    for (char c : s.toCharArray()) {
      if (ss.contains(c)) {
        ++ans;
        ss.clear();
      }
      ss.add(c);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int partitionString(string s) {
    unordered_set<char> ss;
    int ans = 1;
    for (char c : s) {
      if (ss.count(c)) {
        ++ans;
        ss.clear();
      }
      ss.insert(c);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def partitionString(self, s: str) -> int: ss = set() ans = 1 for c in s: if c in ss: ans += 1 ss = set() ss . add(c) return ans

```