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).
1import java.util.HashSet;
2
3public class Solution {
4 public int minSubstrings(String s) {
5 HashSet<Character> seen = new HashSet<>();
6 int count = 0;
7
8 for (char c : s.toCharArray()) {
9 if (seen.contains(c)) {
10 count++;
11 seen.clear(); // Reset
12 }
13 seen.add(c);
14 }
15 return count + 1;
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 System.out.println(sol.minSubstrings("abacaba")); // Output: 4
21 }
22}We use a HashSet to manage the characters in the current substring, clearing it upon detecting a repeat.
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.