Count of non | JavaScript Program to implement the above approach ; Define the dp table globally ; Recursive function to calculate total number of valid non - decreasing strings ; If already calculated state ; Base Case ; Stores the total count of strings formed ; Fill the value in dp matrix ; Function to find the total number of non - decreasing string formed by replacing the ' ? ' ; Initialize all value of dp table with - 1 ; Left and Right limits ; Iterate through all the characters of the string S ; Change R to the current character ; Call the recursive function ; Change L to R and R to 9 ; Reinitialize the length of ? to 0 ; Increment the length of the segment ; Update the ans ; Return the total count ; Driver Code
let MAXN = 100005 let dp = new Array ( MAXN ) . fill ( new Array ( 10 ) ) ; function solve ( len , gap ) { if ( dp [ len ] [ gap ] != - 1 ) { return dp [ len ] [ gap ] ; } if ( len == 0 gap == 0 ) { return 1 ; } if ( gap < 0 ) { return 0 ; } let ans = 0 ; for ( let i = 0 ; i <= gap ; i ++ ) { ans += solve ( len - 1 , gap - i ) ; } return dp [ len ] [ gap ] = ans ; } function countValidStrings ( S ) { for ( let i = 0 ; i < dp . length ; i ++ ) { for ( let j = 0 ; j < dp [ i ] . length ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } let N = S . length ; let L = 1 , R = 9 ; let cnt = 0 ; let ans = 1 ; for ( let i = 0 ; i < N ; i ++ ) { if ( S [ i ] != ' ' ) { R = S . charCodeAt ( i ) - ' ' . charCodeAt ( 0 ) ; ans *= solve ( cnt , R - L ) ; L = R ; R = 9 ; cnt = 0 ; } else { cnt ++ ; } } ans *= solve ( cnt , R - L ) ; return ans ; } let S = " " ; document . write ( countValidStrings ( S ) ) ;