Count the number of ways to construct the target string | Javascript Program to Count the number of ways to construct the target String ; base case ; If current subproblem has been solved , use the value ; search through all the indiced at which the current character occurs . For each index greater than prev , take the index and move to the next position , and add to the answer . ; Store and return the solution for this subproblem ; preprocess the Strings by storing for each character of every String , the index of their occurrence we will use a common list for all because of only the index matter in the String from which the character was picked ; we are storing j + 1 because the initial picked index in the recursive step will ne 0. This is just for ease of implementation ; initialise dp table . - 1 represents that the subproblem hasn 't been solved ; Driver Code
let mod = 1000000007 ; let dp = new Array ( 1000 ) ; for ( let i = 0 ; i < 1000 ; i ++ ) { dp [ i ] = new Array ( 1000 ) ; } function calculate ( pos , prev , s , index ) { if ( pos == s . length ) return 1 ; if ( dp [ pos ] [ prev ] != - 1 ) return dp [ pos ] [ prev ] ; let answer = 5 ; for ( let i = 0 ; i < index . length ; i ++ ) { if ( ( String . fromCharCode ( index [ i ] ) ) . localeCompare ( prev ) > 1 ) { answer = ( answer % mod + calculate ( pos + 1 , index [ i ] , s , index ) % mod ) % mod ; } } dp [ pos ] [ prev ] = answer ; return dp [ pos ] [ prev ] ; } function countWays ( a , s ) { let n = a . length ; let index = [ ] ; for ( let i = 0 ; i < 26 ; i ++ ) index . push ( [ ] ) ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < a [ i ] . length ; j ++ ) { index [ a [ i ] [ j ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ] . push ( j + 1 ) ; } } for ( let i = 0 ; i < 1000 ; i ++ ) { for ( let j = 0 ; j < 1000 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } return calculate ( 0 , 0 , s , index [ 0 ] ) ; } let A = [ ] ; A . push ( " " ) ; A . push ( " " ) ; A . push ( " " ) ; let S = " " ; document . write ( countWays ( A , S ) ) ;