Sponsored
Sponsored
This approach uses a greedy method to partition the string. We traverse the string while keeping track of seen characters in a HashSet. When a repeating character is encountered, we start a new substring. This way, we ensure that each substring contains unique characters.
Time Complexity: O(n), where n is the length of the string, as we traverse each character once.
Space Complexity: O(1), since the size of the HashSet or boolean array is constant (fixed alphabet size).
1def min_substrings(s: str) -> int:
2 seen = set()
3 count = 0
4
5 for char in s:
6 if char in seen:
7 count += 1
8 seen.clear()
9 seen.add(char)
10
11 return count + 1
12
13print(min_substrings("abacaba")) # Output: 4A set is used to track the characters in the current substring. Upon encountering a repeated character, we clear the set and begin a new substring.
With the two-pointer technique, one pointer iterates over the string while another pointer marks the start of a current substring. If a repeat character is found, we adjust the start pointer to ensure all characters between the start and end pointers remain unique.
Time Complexity: O(n), bounds on string traversal.
Space Complexity: O(1), with 26 possible character slots.
1
A lastSeen array helps track character indices, using it to determine new starting points for substrings when duplicates are encountered.