Given string ‘s’, the task is to divide a given string s into multiple substrings, with each substring containing only unique characters. This means that no character should be repeated within a single substring. The goal is to find the minimum number of such substrings required to satisfy this condition.
Examples:
Input: s = “abacaba”
Output: 4
Explanation: Two possible partitions are (“a”, “ba”, “cab”, “a”) and (“ab”, “a”, “ca”, “ba”). It can be shown that 4 is the minimum number of substrings needed.Input: s = “ssssss”
Output: 6
Explanation: The only valid partition is (“s”, “s”, “s”, “s”, “s”, “s”).
Naive Approach: The basic way to solve the problem follows the below idea:
- We initialize an empty set and iterate through the given string. For each character encountered, we check if it is already present in the set.
- If it is, this means that we need to start a new substring since the current substring has a repeated character. We increase our answer variable and clear the set to start a new substring. We then add the current character to the set.
- After iterating through the entire string, the value of the answer variable gives us the minimum number of substrings required to partition the given string such that each substring has unique characters.
Below is the implementation for the above approach:
C++
// C++ program to Finding minimum number// of Substrings with unique Characters#include <bits/stdc++.h>using namespace std;// Function to Find Minimum Number of// Substrings with Unique Charactersint partitionString(string s){ // Create an unordered set to // store unique characters unordered_set<char> st; // Initialize the answer // variable to 1 int ans = 1; // Iterate through the given string for (int i = 0; i < s.size(); i++) { // Check if the current character // is already present in the set if (st.find(s[i]) != st.end()) { // If it is, increment the // answer variable and clear // the set to start a // new substring ans++; st.clear(); } // Add the current character // to the set st.insert(s[i]); } // Return the answer variable, which // gives the minimum number // of substrings required return ans;}// Drivers codeint main(){ string S = "abacaba"; // Function Call cout << "Minimum Number of Substrings with Unique " "Characters: " << partitionString(S); return 0;} |
Java
// Java program to Finding Minimum Number of Substrings with// Unique Charactersimport java.util.*;// Function to Find Minimum Number of Substrings with Unique// Charactersclass GFG { static int partitionString(String s) { // Create a HashSet to store unique characters Set<Character> set = new HashSet<>(); // Initialize the answer variable to 1 int ans = 1; // Iterate through the given string for (int i = 0; i < s.length(); i++) { // Check if the current character is already // present in the set if (set.contains(s.charAt(i))) { // If it is, increment the answer variable // and clear the set to start a new // substring ans++; set.clear(); } // Add the current character to the set set.add(s.charAt(i)); } // Return the answer variable, which gives the // minimum number of substrings required return ans; } public static void main(String[] args) { String S = "abacaba"; System.out.print(partitionString(S)); }}// This code is contributed by Ravi Singh |
Python3
# Function to Find Minimum Number of# Substrings with Unique Charactersdef partitionString(s): # Create an unordered set to # store unique characters st = set() # Initialize the answer # variable to 1 ans = 1 # Iterate through the given string for i in range(len(s)): # Check if the current character # is already present in the set if s[i] in st: # If it is, increment the # answer variable and clear # the set to start a # new substring ans += 1 st.clear() # Add the current character # to the set st.add(s[i]) # Return the answer variable, which # gives the minimum number # of substrings required return ans# Drivers codeS = "abacaba"# Function Callprint("Minimum Number of Substrings with Unique Characters:", partitionString(S)) |
C#
// C# program to Finding Minimum Number of Substrings with// Unique Charactersusing System;using System.Collections.Generic;public class GFG { static int partitionString(string s) { // Create a HashSet to store unique characters HashSet<char> set = new HashSet<char>(); // Initialize the answer variable to 1 int ans = 1; // Iterate through the given string for (int i = 0; i < s.Length; i++) { // Check if the current character is already // present in the set if (set.Contains(s[i])) { // If it is, increment the answer variable // and clear the set to start a new // substring ans++; set.Clear(); } // Add the current character to the set set.Add(s[i]); } // Return the answer variable, which gives the // minimum number of substrings required return ans; } static public void Main() { // Code String S = "abacaba"; Console.Write("Minimum Number of Substrings with Unique Characters: " + partitionString(S)); }}// THis code is contributed by karthik |
Javascript
// JavaScript program to Finding minimum number// of Substrings with unique Characters// Function to Find Minimum Number of Substrings with Unique// Charactersfunction partitionString(s) { // Create a set to store unique characters let st = new Set(); // Initialize the answer // variable to 1 let ans = 1; // Iterate through the given string for (let i = 0; i < s.length; i++) { // Check if the current character // is already present in the set if (st.has(s[i])) { // If it is, increment the // answer variable and clear // the set to start a // new substring ans++; st.clear(); } // Add the current character // to the set st.add(s[i]); } // Return the answer variable, which // gives the minimum number // of substrings required return ans;}// Driver codelet S = "abacaba";// Function Callconsole.log( "Minimum Number of Substrings with Unique Characters: " + partitionString(S)); |
Output
Minimum Number of Substrings with Unique Characters: 4
Time Complexity: O(n) where n is the length of the input string.
Auxiliary Space: O(n) in the worst case This is because we store each character of the input string in the hash set, and in the worst case, all characters of the string are unique.
Efficient Approach: To solve the problem using a Greedy approach follow the below idea:
To solve this problem, we need to keep track of the last occurrence of each character in the string s. Whenever we encounter a repeated character, we know that the current substring contains a character that is repeated, so we need to start a new substring. We can determine the start of the new substring by setting the value of start to the index of the repeated character. We also increased the value of ans to indicate that we have started a new substring.
Below are the steps for the above approach:
- Create an array list of size 26 to store the last index of each character (initially set to -1).
Initialize the starting index of the current substring to 0. - Initialize the answer variable ans to 1.
- Iterate through the given string s:
- Get the index of the current character in the array by subtracting ‘a’ from it.
- Check if the current character is already present in the current substring by comparing its last index with the starting index of the current substring.
- If it is, increment the answer variable ans and update the starting index of the new substring to the current index.
- Update the last index of the current character in the array with the current index.
- Return the answer variable ans, which gives the minimum number of substrings required.
Below is the implementation for the above approach:
C++
// C++ program to Finding Minimum// Number of Substrings with// Unique Characters#include <bits/stdc++.h>using namespace std;// Function to Find Minimum Number of// Substrings with Unique charactersint partitionString(string s){ // Create an array to store the // last index of each character vector<int> last(26, -1); // Initialize the starting index // of the current substring to 0 int start = 0; // Initialize the answer variable to 1 int ans = 1; // Iterate through the given string for (int i = 0; i < s.length(); i++) { // Get the index of the current // character in the array int index = s[i] - 'a'; // Check if the current character // is already present in the // current substring if (last[index] >= start) { // If it is, increment the answer // variable and update the // starting index of the // new substring ans++; start = i; } // Update the last index // of the current character last[index] = i; } // Return the answer variable, which // gives the minimum number of // substrings required return ans;}// Drivers codeint main(){ string S = "abacaba"; // Function Call cout << "Minimum Number of Substrings with Unique " "Characters: " << partitionString(S); return 0;} |
Java
// Java program to Finding Minimum Number of Substrings with// Unique Charactersimport java.util.*;// Function to Find Minimum Number of Substrings with Unique// Charactersclass GFG { static int partitionString(String s) { // Create an array to store the last index of each // character int[] last = new int[26]; Arrays.fill(last, -1); // Initialize the starting index of the current // substring to 0 int start = 0; // Initialize the answer variable to 1 int ans = 1; // Iterate through the given string for (int i = 0; i < s.length(); i++) { // Get the index of the current character in the // array int index = s.charAt(i) - 'a'; // Check if the current character is already // present in the current substring if (last[index] >= start) { // If it is, increment the answer variable // and update the starting index of the new // substring ans++; start = i; } // Update the last index of the current // character last[index] = i; } // Return the answer variable, which gives the // minimum number of substrings required return ans; } public static void main(String[] args) { String S = "ssssss"; System.out.print(partitionString(S)); }}// This code is contributed by Ravi Singh |
Python3
# Function to Find Minimum Number of# Substrings with Unique charactersdef partitionString(s): # Create an array to store the # last index of each character last = [-1] * 26 # Initialize the starting index # of the current substring to 0 start = 0 # Initialize the answer variable to 1 ans = 1 # Iterate through the given string for i in range(len(s)): # Get the index of the current # character in the array index = ord(s[i]) - ord('a') # Check if the current character # is already present in the # current substring if last[index] >= start: # If it is, increment the answer # variable and update the # starting index of the # new substring ans += 1 start = i # Update the last index # of the current character last[index] = i # Return the answer variable, which # gives the minimum number of # substrings required return ans# Drivers codeif __name__ == '__main__': S = "abacaba" # Function Call print("Minimum Number of Substrings with Unique Characters: ", partitionString(S)) |
C#
using System;using System.Collections.Generic;public class Program{ // Function to find minimum number of substrings with unique characters public static int PartitionString(string s) { // Create a dictionary to store the last index of each character Dictionary<char, int> last = new Dictionary<char, int>(); // Initialize the starting index of the current substring to 0 int start = 0; // Initialize the answer variable to 1 int ans = 1; // Iterate through the given string for (int i = 0; i < s.Length; i++) { char c = s[i]; // Check if the current character is // already present in the current substring if (last.ContainsKey(c) && last >= start) { // If it is, increment the answer variable and // update the starting index of the new substring ans++; start = i; } // Update the last index of the current character last = i; } // Return the answer variable, which gives // the minimum number of substrings required return ans; } // Driver's code public static void Main() { string S = "abacaba"; // Function call Console.WriteLine("Minimum Number of Substrings with Unique Characters: " + PartitionString(S)); }}// This code is contributed by Prajwal Kandekar |
Javascript
// JavaScript program to Finding Minimum// Number of Substrings with// Unique Charactersfunction partitionString(s) { // Create an array to store the // last index of each character const last = new Array(26).fill(-1); // Initialize the starting index // of the current substring to 0 let start = 0; // Initialize the answer variable to 1 let ans = 1; // Iterate through the given string for (let i = 0; i < s.length; i++) { // Get the index of the current // character in the array const index = s.charCodeAt(i) - 97; // Check if the current character // is already present in the // current substring if (last[index] >= start) { // If it is, increment the answer // variable and update the // starting index of the // new substring ans++; start = i; } // Update the last index // of the current character last[index] = i; } // Return the answer variable, which // gives the minimum number of // substrings required return ans;}// Example usageconst S = "abacaba";console.log(`Minimum Number of Substrings with Unique Characters: ${partitionString(S)}`); |
Output
Minimum Number of Substrings with Unique Characters: 4
Time Complexity: O(n) where n is the length of the input string.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
