source: https://leetcode.com/problems/optimal-partition-of-string/description/
Optimal Partition of String
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public int partitionString(String s) { HashSet<Character> set = new HashSet<>(); int count=1; for(char c: s.toCharArray()){ //if the set contains a character //increase the count by 1 //and clear the set if(set.contains(c)){ count++; set.clear(); } set.add(c); } return count; } } |
Let’s say n is the number of characters in a string
Time Complexity
O(n), as we need to iterate over the entire string
Space Complexity
O(n), to store the characters in a HashSet