Count number of ways to convert string S to T by performing K cyclic shifts | JavaScript program for the above approach ; Function to count number of ways to convert string S to string T by performing K cyclic shifts ; Calculate length of string ; ' a ' is no of good cyclic shifts ' b ' is no of bad cyclic shifts ; Iterate in the string ; Precompute the number of good and bad cyclic shifts ; dp2 [ i ] to store the no of ways to get to a bad shift in i moves ; Calculate good and bad shifts ; Return the required number of ways ; Given Strings ; Given K shifts required ; Function Call
let mod = 10000000007 ; function countWays ( s , t , k ) { let n = s . length ; let a = 0 , b = 0 ; for ( let i = 0 ; i < n ; i ++ ) { let p = s . substr ( i , n - i ) + s . substr ( 0 , i ) ; if ( p == t ) a ++ ; else b ++ ; } let dp1 = Array . from ( { length : k + 1 } , ( _ , i ) => 0 ) ; let dp2 = Array . from ( { length : k + 1 } , ( _ , i ) => 0 ) ; if ( s == t ) { dp1 [ 0 ] = 1 ; dp2 [ 0 ] = 0 ; } else { dp1 [ 0 ] = 0 ; dp2 [ 0 ] = 1 ; } for ( let i = 1 ; i <= k ; i ++ ) { dp1 [ i ] = ( ( dp1 [ i - 1 ] * ( a - 1 ) ) % mod + ( dp2 [ i - 1 ] * a ) % mod ) % mod ; dp2 [ i ] = ( ( dp1 [ i - 1 ] * ( b ) ) % mod + ( dp2 [ i - 1 ] * ( b - 1 ) ) % mod ) % mod ; } return dp1 [ k ] ; } let S = " " , T = " " ; let K = 2 ; document . write ( countWays ( S , T , K ) ) ;