text: Minimum number of substrings the given string can be splitted into that satisfy the given conditions | C ++ implementation of the approach ; Set to store all the strings from the given array ; To store the required count ; 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 ; All the chosen substrings are present in the map ; Update the minimum count of substrings ; Starting from the substrings of length 1 that start with the given index ; Get the substring ; If the substring is present in the set ; Recursive call for the rest of the string ; 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 ; Insert all the strings from the given array in a set ; Find the required count ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; unordered_set < string > uSet ; int minCnt = INT_MAX ; void findSubStr ( string str , int cnt , int start ) { if ( start == str . length ( ) ) { minCnt = min ( cnt , minCnt ) ; } for ( int len = 1 ; len <= ( str . length ( ) - start ) ; len ++ ) { string subStr = str . substr ( start , len ) ; if ( uSet . find ( subStr ) != uSet . end ( ) ) { findSubStr ( str , cnt + 1 , start + len ) ; } } } void findMinSubStr ( string arr [ ] , int n , string str ) { for ( int i = 0 ; i < n ; i ++ ) uSet . insert ( arr [ i ] ) ; findSubStr ( str , 0 , 0 ) ; } 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 ; }