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).
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5int minSubstrings(char *s) {
6 bool seen[26] = { false };
7 int count = 0;
8
9 for (int i = 0; s[i] != '\0'; ++i) {
10 if (seen[s[i] - 'a']) {
11 memset(seen, 0, sizeof(seen)); // Reset seen characters
12 count++;
13 }
14 seen[s[i] - 'a'] = true;
15 }
16 return count + 1;
17}
18
19int main() {
20 char s[] = "abacaba";
21 printf("%d\n", minSubstrings(s)); // Output: 4
22 return 0;
23}We use an array seen to keep track of which characters have been encountered in the current substring. When a repeated character is found, we reset the array and increment the substring count.
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.
1using System;
public class Solution {
public int MinSubstrings(string s) {
int[] lastSeen = new int[26];
for (int i = 0; i < 26; ++i) lastSeen[i] = -1;
int start = 0, count = 1;
for (int i = 0; i < s.Length; ++i) {
if (lastSeen[s[i] - 'a'] >= start) {
count++;
start = i;
}
lastSeen[s[i] - 'a'] = i;
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinSubstrings("abacaba")); // Output: 4
}
}This method utilizes an integer array lastSeen to track character indices for optimizing substring formations.