#2405
Optimal Partition of String
pupil · 455 · lc medium +26 · verified · 78.4% accepted · 2,809 likes · top 90%
Description
Given a string s, partition it into the minimum number of substrings such that no character appears in more than one substring.
Return the minimum number of substrings in such 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").
Code
1
2
3