Minimum number of swaps required to make the string K periodic | Python3 code to find the minimum number of swaps required to make the string K periodic ; Mark all allowed characters as true ; Initialize the freq array to 0 ; Increase the frequency of each character ; Total number of periods of size K in the string ; Check if the current character is present in allowed and whether the current frequency is greater than all previous frequencies for this position ; Update the answer by subtracting the maxfrequency from total positions if there exist extra character at the end of the string apart from the n / k characters then add 1. ; Driver code
def minFlip ( s , n , k , a , p ) : NEW_LINE INDENT allowed = [ 0 ] * 26 NEW_LINE for i in range ( p ) : NEW_LINE INDENT allowed [ ord ( a [ i ] ) - ord ( ' a ' ) ] = True NEW_LINE DEDENT freq = [ [ 0 for x in range ( 26 ) ] for y in range ( k ) ] NEW_LINE for i in range ( k ) : NEW_LINE INDENT for j in range ( 26 ) : NEW_LINE INDENT freq [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT freq [ i % k ] [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE totalpositions = n // k NEW_LINE for i in range ( k ) : NEW_LINE INDENT maxfrequency = 0 NEW_LINE for j in range ( 26 ) : NEW_LINE INDENT if ( freq [ i ] [ j ] > maxfrequency and allowed [ j ] == True ) : NEW_LINE INDENT maxfrequency = freq [ i ] [ j ] NEW_LINE DEDENT DEDENT ans += ( totalpositions - maxfrequency ) NEW_LINE if ( i % k < n % k ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " nihsiakyt " NEW_LINE n = len ( S ) NEW_LINE K = 3 NEW_LINE A = [ ' n ' , ' i ' , ' p ' , ' s ' , ' q ' ] NEW_LINE p = len ( A ) NEW_LINE minFlip ( S , n , K , A , p ) NEW_LINE DEDENT