Minimum replacements to make adjacent characters unequal in a ternary string | Set | Python 3 program to count the minimal replacements such that adjacent characters are unequal ; function to return integer value of i - th character in the string ; Function to count the number of minimal replacements ; If the string has reached the end ; If the state has been visited previously ; Get the current value of character ; If it is equal then change it ; All possible changes ; Change done ; If same no change ; Driver Code ; Length of string ; Create a DP array ; First character ; Function to find minimal replacements
import sys NEW_LINE def charVal ( s , i ) : NEW_LINE INDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif ( s [ i ] == '1' ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT else : NEW_LINE INDENT return 2 NEW_LINE DEDENT DEDENT def countMinimalReplacements ( s , i , prev , dp , n ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ prev ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ prev ] NEW_LINE DEDENT val = charVal ( s , i ) NEW_LINE ans = sys . maxsize NEW_LINE if ( val == prev ) : NEW_LINE INDENT val = 0 NEW_LINE for cur in range ( 3 ) : NEW_LINE INDENT if ( cur == prev ) : NEW_LINE INDENT continue NEW_LINE DEDENT val = 1 + countMinimalReplacements ( s , i + 1 , cur , dp , n ) NEW_LINE ans = min ( ans , val ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT ans = countMinimalReplacements ( s , i + 1 , val , dp , n ) NEW_LINE DEDENT dp [ i ] [ val ] = ans NEW_LINE return dp [ i ] [ val ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = "201220211" NEW_LINE n = len ( s ) NEW_LINE dp = [ [ - 1 for i in range ( 3 ) ] for i in range ( n ) ] NEW_LINE val = charVal ( s , 0 ) NEW_LINE print ( countMinimalReplacements ( s , 1 , val , dp , n ) ) NEW_LINE DEDENT