Minimum replacements to make adjacent characters unequal in a ternary string | Set | C ++ 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 ; else If same no change ; Driver Code ; Length of string ; Create a DP array ; First character ; Function to find minimal replacements
#include <bits/stdc++.h> NEW_LINE using namespace std ; int charVal ( string s , int i ) { if ( s [ i ] == '0' ) return 0 ; else if ( s [ i ] == '1' ) return 1 ; else return 2 ; } int countMinimalReplacements ( string s , int i , int prev , int dp [ ] [ 3 ] , int n ) { if ( i == n ) { return 0 ; } if ( dp [ i ] [ prev ] != -1 ) return dp [ i ] [ prev ] ; int val = charVal ( s , i ) ; int ans = INT_MAX ; if ( val == prev ) { int val = 0 ; for ( int cur = 0 ; cur <= 2 ; cur ++ ) { if ( cur == prev ) continue ; val = 1 + countMinimalReplacements ( s , i + 1 , cur , dp , n ) ; ans = min ( ans , val ) ; } } ans = countMinimalReplacements ( s , i + 1 , val , dp , n ) ; return dp [ i ] [ val ] = ans ; } int main ( ) { string s = "201220211" ; int n = s . length ( ) ; int dp [ n ] [ 3 ] ; memset ( dp , -1 , sizeof dp ) ; int val = charVal ( s , 0 ) ; cout << countMinimalReplacements ( s , 1 , val , dp , n ) ; return 0 ; }