Count number of ways to convert string S to T by performing K cyclic shifts | Python3 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 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
mod = 1000000007 NEW_LINE def countWays ( s , t , k ) : NEW_LINE INDENT n = len ( s ) NEW_LINE a = 0 NEW_LINE b = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT p = s [ i : n - i + 1 ] + s [ : i + 1 ] NEW_LINE if ( p == t ) : NEW_LINE INDENT a += 1 NEW_LINE DEDENT else : NEW_LINE INDENT b += 1 NEW_LINE DEDENT DEDENT dp1 = [ 0 ] * ( k + 1 ) NEW_LINE dp2 = [ 0 ] * ( k + 1 ) NEW_LINE if ( s == t ) : NEW_LINE INDENT dp1 [ 0 ] = 1 NEW_LINE dp2 [ 0 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT dp1 [ 0 ] = 0 NEW_LINE dp2 [ 0 ] = 1 NEW_LINE DEDENT for i in range ( 1 , k + 1 ) : NEW_LINE INDENT dp1 [ i ] = ( ( dp1 [ i - 1 ] * ( a - 1 ) ) % mod + ( dp2 [ i - 1 ] * a ) % mod ) % mod NEW_LINE dp2 [ i ] = ( ( dp1 [ i - 1 ] * ( b ) ) % mod + ( dp2 [ i - 1 ] * ( b - 1 ) ) % mod ) % mod NEW_LINE DEDENT return ( dp1 [ k ] ) NEW_LINE DEDENT S = ' ab ' NEW_LINE T = ' ab ' NEW_LINE K = 2 NEW_LINE print ( countWays ( S , T , K ) ) NEW_LINE