Is Optimal Partition of String easy or hard?

Optimal Partition of String is categorized as a Medium difficulty problem. The implementation is straightforward once you recognize the greedy rule: start a new substring whenever a duplicate character appears.

Optimal Partition of String Python/Java solution

In Python, a set is used to store characters of the current substring while iterating through the string. In Java, a HashSet or a boolean array of size 26 is commonly used. Both implementations follow the same greedy logic and run in O(n) time.

How to solve Optimal Partition of String in O(n)?

Iterate through the string while storing characters of the current substring in a HashSet or boolean array. If the next character already exists, increment the partition counter and reset the data structure. Continue scanning until the end. Each character is handled once, giving O(n) time complexity.

What is the best approach for Optimal Partition of String?

The greedy approach using a HashSet is the most common and intuitive solution. Traverse the string once and keep track of characters in the current substring. When a duplicate character appears, increment the partition count and reset the set. This produces the minimum number of partitions in O(n) time and O(1) space.

Is Optimal Partition of String asked at Google/Amazon/Meta?

This problem follows common interview patterns around greedy string processing and hash-based duplicate detection. Variations of substring partitioning and sliding window uniqueness checks appear in interviews at companies like Amazon, Google, and Meta.

What data structure is used in Optimal Partition of String?

A HashSet or a fixed-size boolean array is typically used to track characters currently in the substring. These structures allow O(1) membership checks, which is critical for detecting duplicates efficiently while scanning the string.

What is the time complexity of Optimal Partition of String?

The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once and HashSet lookups take constant time on average. Space complexity is O(1) because at most 26 lowercase letters are stored.

Description Hints 2 Solution Video 6:48

2405. Optimal Partition of String

Medium78.0% acceptance4 companies

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 <= 10⁵
s consists of only English lowercase letters.

Asked at 4 companies

Microsoft

IBM Amazon

Google

Topics

Hints open one at a time

Hint 1

Try to come up with a greedy approach.

Hint 2

From left to right, extend every substring in the partition as much as possible.

6:48

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution