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).
1function minSubstrings(s) {
2 const seen = new Set();
3 let count = 0;
4
5 for (const char of s) {
6 if (seen.has(char)) {
7 count++;
8 seen.clear();
9 }
10 seen.add(char);
11 }
12 return count + 1;
13}
14
15console.log(minSubstrings("abacaba")); // Output: 4A Set allows tracking of seen characters in the current substring, initiating a new substring when repetition occurs.
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#include <vector>
using namespace std;
int minSubstrings(string s) {
vector<int> lastSeen(26, -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;
}
int main() {
string s = "abacaba";
cout << minSubstrings(s) << endl; // Output: 4
return 0;
}Using a vector lastSeen to track the most recent index of each character and adjusting pointers helps maintain unique substrings efficiently.