Minimum number of substrings the given string can be splitted into that satisfy the given conditions
Given a string str and a string array arr[], the task is to find the minimum count of substrings this can be split into such that every substring is present in the given string array arr[].
Examples:
Input: str = β111112β, arr[] = {β11β, β111β, β11111β, β2β}
Output: 2
β11111β and β2β are the required substrings.
β11β, β111β and β2β can also be a valid answer
but it is not the minimum.Input: str = β123456β, arr[] = {β1β, β12345β, β2345β, β56β, β23β, β456β}
Output: 3
Approach: Iterate the string from index 0 and build the prefix string, if the prefix string exists in the given array (a set can be used to check this) then call the function again from the next position in the string and keep track of the overall minimum count of substrings.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Set to store all the strings // from the given array unordered_set<string> uSet; // To store the required count int minCnt = INT_MAX; // Recursive function to find the count of // substrings that can be splitted starting // from the index start such that all // the substrings are present in the map void findSubStr(string str, int cnt, int start) { // All the chosen substrings // are present in the map if (start == str.length()) { // Update the minimum count // of substrings minCnt = min(cnt, minCnt); } // Starting from the substrings of length 1 // that start with the given index for ( int len = 1; len <= (str.length() - start); len++) { // Get the substring string subStr = str.substr(start, len); // If the substring is present in the set if (uSet.find(subStr) != uSet.end()) { // Recursive call for the // rest of the string findSubStr(str, cnt + 1, start + len); } } } // Function that inserts all the strings // from the given array in a set and calls // the recursive function to find the // minimum count of substrings str can be // splitted into that satisfy the given condition void findMinSubStr(string arr[], int n, string str) { // Insert all the strings from // the given array in a set for ( int i = 0; i < n; i++) uSet.insert(arr[i]); // Find the required count findSubStr(str, 0, 0); } // Driver code int main() { string str = "123456" ; string arr[] = { "1" , "12345" , "2345" , "56" , "23" , "456" }; int n = sizeof (arr) / sizeof (string); findMinSubStr(arr, n, str); cout << minCnt; return 0; } |
Java
//Java implementation of above approach import java.util.*; class GFG { // Set to store all the Strings // from the given array static Set<String> uSet = new HashSet<String>(); // To store the required count static int minCnt = Integer.MAX_VALUE; // Recursive function to find the count of // subStrings that can be splitted starting // from the index start such that all // the subStrings are present in the map static void findSubStr(String str, int cnt, int start) { // All the chosen subStrings // are present in the map if (start == str.length()) { // Update the minimum count // of subStrings minCnt = Math.min(cnt, minCnt); } // Starting from the subStrings of length 1 // that start with the given index for ( int len = 1 ; len <= (str.length() - start); len++) { // Get the subString String subStr = str.substring(start, start + len); // If the subString is present in the set if (uSet.contains(subStr)) { // Recursive call for the // rest of the String findSubStr(str, cnt + 1 , start + len); } } } // Function that inserts all the Strings // from the given array in a set and calls // the recursive function to find the // minimum count of subStrings str can be // splitted into that satisfy the given condition static void findMinSubStr(String arr[], int n, String str) { // Insert all the Strings from // the given array in a set for ( int i = 0 ; i < n; i++) uSet.add(arr[i]); // Find the required count findSubStr(str, 0 , 0 ); } // Driver code public static void main(String args[]) { String str = "123456" ; String arr[] = { "1" , "12345" , "2345" , "56" , "23" , "456" }; int n = arr.length; findMinSubStr(arr, n, str); System.out.print(minCnt); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach import sys # Set to store all the strings # from the given array uSet = set (); # To store the required count minCnt = sys.maxsize; # Recursive function to find the count of # substrings that can be splitted starting # from the index start such that all # the substrings are present in the map def findSubStr(string, cnt, start) : global minCnt; # All the chosen substrings # are present in the map if (start = = len (string)) : # Update the minimum count # of substrings minCnt = min (cnt, minCnt); # Starting from the substrings of length 1 # that start with the given index for length in range ( 1 , len (string) - start + 1 ) : # Get the substring subStr = string[start : start + length]; # If the substring is present in the set if subStr in uSet : # Recursive call for the # rest of the string findSubStr(string, cnt + 1 , start + length); # Function that inserts all the strings # from the given array in a set and calls # the recursive function to find the # minimum count of substrings str can be # splitted into that satisfy the given condition def findMinSubStr(arr, n, string) : # Insert all the strings from # the given array in a set for i in range (n) : uSet.add(arr[i]); # Find the required count findSubStr(string, 0 , 0 ); # Driver code if __name__ = = "__main__" : string = "123456" ; arr = [ "1" , "12345" , "2345" , "56" , "23" , "456" ]; n = len (arr); findMinSubStr(arr, n, string); print (minCnt); # This code is contributed by AnkitRai01 |
C#
// C# implementation of above approach using System; using System.Collections.Generic; class GFG { // Set to store all the Strings // from the given array static HashSet<String> uSet = new HashSet<String>(); // To store the required count static int minCnt = int .MaxValue; // Recursive function to find the count of // subStrings that can be splitted starting // from the index start such that all // the subStrings are present in the map static void findSubStr(String str, int cnt, int start) { // All the chosen subStrings // are present in the map if (start == str.Length) { // Update the minimum count // of subStrings minCnt = Math.Min(cnt, minCnt); } // Starting from the subStrings of length 1 // that start with the given index for ( int len = 1; len <= (str.Length - start); len++) { // Get the subString String subStr = str.Substring(start, len); // If the subString is present in the set if (uSet.Contains(subStr)) { // Recursive call for the // rest of the String findSubStr(str, cnt + 1, start + len); } } } // Function that inserts all the Strings // from the given array in a set and calls // the recursive function to find the // minimum count of subStrings str can be // splitted into that satisfy the given condition static void findMinSubStr(String []arr, int n, String str) { // Insert all the Strings from // the given array in a set for ( int i = 0; i < n; i++) uSet.Add(arr[i]); // Find the required count findSubStr(str, 0, 0); } // Driver code public static void Main(String []args) { String str = "123456" ; String []arr = { "1" , "12345" , "2345" , "56" , "23" , "456" }; int n = arr.Length; findMinSubStr(arr, n, str); Console.WriteLine(minCnt); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Set to store all the strings // from the given array var uSet = new Set(); // To store the required count var minCnt = 1000000000; // Recursive function to find the count of // substrings that can be splitted starting // from the index start such that all // the substrings are present in the map function findSubStr( str, cnt, start) { // All the chosen substrings // are present in the map if (start == str.length) { // Update the minimum count // of substrings minCnt = Math.min(cnt, minCnt); } // Starting from the substrings of length 1 // that start with the given index for ( var len = 1; len <= (str.length - start); len++) { // Get the substring var subStr = str.substring(start, start+len); // If the substring is present in the set if (uSet.has(subStr)) { // Recursive call for the // rest of the string findSubStr(str, cnt + 1, start + len); } } } // Function that inserts all the strings // from the given array in a set and calls // the recursive function to find the // minimum count of substrings str can be // splitted into that satisfy the given condition function findMinSubStr(arr, n, str) { // Insert all the strings from // the given array in a set for ( var i = 0; i < n; i++) uSet.add(arr[i]); // Find the required count findSubStr(str, 0, 0); } // Driver code var str = "123456" ; var arr = [ "1" , "12345" , "2345" , "56" , "23" , "456" ]; var n = arr.length; findMinSubStr(arr, n, str); document.write( minCnt); </script> |
3
Method 2:Using Dynamic Programming
Approach:
we use dp in our approach, we can use the array dp[]. Because the minimum count of substrings up to the first index is always 0 and the minimum count of substrings up to every subsequent index is initially equal to the length of the substring from the beginning of the string to that index, we can initialize dp[0] = 0 and dp[i] to i for i > 0. Finally, dp[len] is returned, where len is the length of the input string str. This will tell us the smallest number of substrings that str can be split into so that each substring is present in arr[].
Implementation:
C++
// C++ Implementation #include <iostream> #include <string> #include <unordered_set> using namespace std; // Function to find minimum substring count int minSubstringCount(string str, string arr[], int n) { int len = str.length(); int dp[len + 1]; dp[0] = 0; unordered_set<string> set(arr, arr + n); // Iterate for ( int i = 1; i <= len; i++) { dp[i] = i; for ( int j = 0; j < i; j++) { // Fetch the substring between indexes string sub = str.substr(j, i - j); if (set.find(sub) != set.end()) { dp[i] = min(dp[i], dp[j] + 1); } } } return dp[len]; } // Driver code int main() { string str = "111112" ; string arr[] = { "11" , "111" , "11111" , "2" }; int n = sizeof (arr) / sizeof (arr[0]); // Function call int result = minSubstringCount(str, arr, n); cout << result << endl; return 0; } |
Java
import java.util.HashSet; public class GFG { // Function to find minimum substring count static int minSubstringCount(String str, String[] arr) { int len = str.length(); // Create an array to store minimum substring count at each index int [] dp = new int [len + 1 ]; dp[ 0 ] = 0 ; // Create a HashSet to store the strings from the array HashSet<String> set = new HashSet<>(); for (String s : arr) { set.add(s); } // Iterate through the string for ( int i = 1 ; i <= len; i++) { dp[i] = i; for ( int j = 0 ; j < i; j++) { // Fetch the substring between indexes String sub = str.substring(j, i); if (set.contains(sub)) { dp[i] = Math.min(dp[i], dp[j] + 1 ); } } } return dp[len]; } // Driver code public static void main(String[] args) { String str = "111112" ; String[] arr = { "11" , "111" , "11111" , "2" }; int result = minSubstringCount(str, arr); System.out.println(result); } } |
Python3
def min_substring_count(s, arr): length = len (s) dp = [i for i in range (length + 1 )] substring_set = set (arr) for i in range ( 1 , length + 1 ): for j in range (i): sub = s[j:i] if sub in substring_set: dp[i] = min (dp[i], dp[j] + 1 ) return dp[length] if __name__ = = "__main__" : s = "111112" arr = [ "11" , "111" , "11111" , "2" ] result = min_substring_count(s, arr) print (result) |
C#
using System; using System.Collections.Generic; class GFG { // Function to find the minimum count of substrings // required to form the given string static int MinSubstringCount( string str, string [] arr, int n) { int len = str.Length; int [] dp = new int [len + 1]; dp[0] = 0; // Base case: an empty string requires 0 // substrings HashSet< string > set = new HashSet< string >( arr); // Store the substrings in a hash set for // faster lookup for ( int i = 1; i <= len; i++) { dp[i] = i; // Initialize dp[i] to the maximum // possible value for ( int j = 0; j < i; j++) { string sub = str.Substring( j, i - j); // Get the substring from // index j to i-1 if ( set .Contains(sub)) { // If the substring is present in the // set, update dp[i] with the minimum // count dp[i] = Math.Min(dp[i], dp[j] + 1); } } } return dp[len]; // Return the minimum count of // substrings required to form the // given string } static void Main( string [] args) { string str = "111112" ; // Given string string [] arr = { "11" , "111" , "11111" , "2" }; // Array of substrings int n = arr.Length; // Length of the array // Find the minimum count of substrings required to // form the given string and print the result int result = MinSubstringCount(str, arr, n); Console.WriteLine(result); } } |
Javascript
// JavaScript Implementation function minSubstringCount(str, arr) { const len = str.length; const dp = new Array(len + 1).fill(0); dp[0] = 0; const set = new Set(arr); // Iterate through the string for (let i = 1; i <= len; i++) { dp[i] = i; for (let j = 0; j < i; j++) { // Fetch the substring between indexes const sub = str.substring(j, i); if (set.has(sub)) { dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[len]; } // Driver code const str = "111112" ; const arr = [ "11" , "111" , "11111" , "2" ]; // Function call const result = minSubstringCount(str, arr); console.log(result); |
2
Time Complexity: O(n^3),where n is the length of the input string str.
Auxiliary Space: O(n)