Split a string into the fewest contiguous parts so that no character appears in more than one part.
Partition Labels
gfgProblem
Given a string s, partition it into one or more contiguous substrings so that each character appears in at most one part.
Return the partitioning that uses the minimum number of parts.
A valid partition means that if a character appears in one part, it cannot appear in any other part. Each part must be non-empty and the parts must cover the entire string in order.
Goal
Determine how to cut the string into the smallest possible number of contiguous segments while preserving the rule that every character belongs to exactly one segment.
Input Format
- A single string
s.
Output Format
- Return the minimum number of contiguous partitions needed so that every character appears in at most one partition.
Constraints
1 <= s.length- The string contains only lowercase English letters when applicable.
- A valid partition must use contiguous substrings and cover the entire string.
Example 1
Input
s = "abac"
Output
2
Explanation
One optimal partition is "aba" | "c". The characters a and b do not appear in more than one part.
Example 2
Input
s = "abcd"
Output
4
Explanation
Every character appears once, so each character can be its own partition: "a" | "b" | "c" | "d".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.