We’re asked to partition a string into a minimum number of substrings such that each substring has no duplicate characters. Defining a substring, its a contiguous sequence of characters within a string - unlike a subsequence which is still character within the same order but not contiguous.
Pretty easy to solve greedily. We maintain a set of characters we’ve seen already, and iterate through all the characters in the original string. If we see a duplicate character, we increment the number of substrings we need to partition, and clear the set.
The solution is as follows:
class Solution:
def partitionString(self, s: str) -> int:
seen, s, ans = set(), list(s), 1
for char in s:
if char in seen:
seen = set()
ans += 1
seen.add(char)
return ans_ Time Complexity:
O(n) - We iterate over each character in s.
_ Space Complexity:
O(n) - We maintain a set of seen characters.