Count number of ways to convert string S to T by performing K cyclic shifts | Java program for 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 ; Driver code ; Given Strings ; Given K shifts required ; Function Call
class GFG { static long mod = 10000000007L ; static long countWays ( String s , String t , int k ) { int n = s . length ( ) ; int a = 0 , b = 0 ; for ( int i = 0 ; i < n ; i ++ ) { String p = s . substring ( i , n - i ) + s . substring ( 0 , i ) ; if ( p == t ) a ++ ; else b ++ ; } long dp1 [ ] = new long [ k + 1 ] ; long dp2 [ ] = new long [ k + 1 ] ; if ( s == t ) { dp1 [ 0 ] = 1 ; dp2 [ 0 ] = 0 ; } else { dp1 [ 0 ] = 0 ; dp2 [ 0 ] = 1 ; } for ( int 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 ] ; } public static void main ( String [ ] args ) { String S = " ab " , T = " ab " ; int K = 2 ; System . out . print ( countWays ( S , T , K ) ) ; } }