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).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MinSubstrings(string s) {
6 HashSet<char> seen = new HashSet<char>();
7 int count = 0;
8
9 foreach (char c in s) {
10 if (seen.Contains(c)) {
11 count++;
12 seen.Clear(); // Reset
13 }
14 seen.Add(c);
15 }
16 return count + 1;
17 }
18
19 public static void Main() {
20 Solution sol = new Solution();
21 Console.WriteLine(sol.MinSubstrings("abacaba")); // Output: 4
22 }
23}We employ a HashSet to manage the current substring's characters, starting a new substring when a duplicate is found.
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.