Back to DSA sheet
Optimal Partition of String
MediumArraysPartition a string into the fewest contiguous substrings such that no substring contains a repeated character.
Input format (stdin): a single line, the string. Output the minimum number of substrings.
Examples
Input: abacaba
Output: 4
e.g. 'ab','ac','ab','a'.
Input: ssssss
Output: 6
Each 's' must be its own piece.
Constraints
- 1 <= length <= 10^5
- lowercase English letters
Sheets
NeetCode 250
optimal-partition-of-string.cpp3 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.