HackMD2405.Optimal Partition of String
tags: Medium,String,Hash Table,Greedy
2405. 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 sconsists of only English lowercase letters.
解答
C++
class Solution {
public:
int partitionString(string s) {
int ans = 1;
string t = "";
for (auto c : s) {
if (t.find(c) < t.length()) {
ans++;
t = "";
}
t += c;
}
return ans;
}
};
Yen-Chi ChenWed, Apr 5, 2023
Python
class Solution:
def partitionString(self, s: str) -> int:
ans = 1
t = ''
for c in s:
if c in t:
ans += 1
t = ''
t += c
return ans
Yen-Chi ChenWed, Apr 5, 2023
