Minimum number of substrings the given string can be splitted into that satisfy the given conditions | Java implementation of above 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
import java . util . * ; class GFG { static Set < String > uSet = new HashSet < String > ( ) ; static int minCnt = Integer . MAX_VALUE ; static void findSubStr ( String str , int cnt , int start ) { if ( start == str . length ( ) ) { minCnt = Math . min ( cnt , minCnt ) ; } for ( int len = 1 ; len <= ( str . length ( ) - start ) ; len ++ ) { String subStr = str . substring ( start , start + len ) ; if ( uSet . contains ( subStr ) ) { findSubStr ( str , cnt + 1 , start + len ) ; } } } static void findMinSubStr ( String arr [ ] , int n , String str ) { for ( int i = 0 ; i < n ; i ++ ) uSet . add ( arr [ i ] ) ; findSubStr ( str , 0 , 0 ) ; } 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 ) ; } }