Given a string of ‘0’, ‘1’, and ‘2’. The task is to find the minimum number of replacements such that the adjacent characters are not equal.
Examples:
Input: s = “201220211”
Output: 2
Resultant string after changes is 201210210Input: s = “0120102”
Output: 0
Approach:
The problem has been solved using a greedy approach in the previous post. In this post, we will discuss a Dynamic Programming approach to solve the same problem. Create a function charVal which returns 0, 1, or 2 depending on the character.
A recursive function is made which calls the charVal function to get the i-th value, and if this is equal to the previous one, then only the other two states (1 or 2, 0 or 1, 0 or 2) are used at i-th character. If it is not equal to the previous one, no changes are made. A dp[][] array is used for memoization. The base case is when all the positions are filled. If any of the states is re-visited, then return the value that is stored in the dp[][] array. DP[i][j] means that i-th position is filled with j-th character.
Below is the implementation of the above problem:
C++
// C++ program to count the minimal // replacements such that adjacent characters // are unequal #include <bits/stdc++.h> using namespace std; // function to return integer value // of i-th character in the string int charVal(string s, int i) { if (s[i] == '0' ) return 0; else if (s[i] == '1' ) return 1; else return 2; } // Function to count the number of // minimal replacements int countMinimalReplacements(string s, int i, int prev, int dp[][3], int n) { // If the string has reached the end if (i == n) { return 0; } // If the state has been visited previously if (dp[i][prev] != -1) return dp[i][prev]; // Get the current value of character int val = charVal(s, i); int ans = INT_MAX; // If it is equal then change it if (val == prev) { int val = 0; // All possible changes for ( int cur = 0; cur <= 2; cur++) { if (cur == prev) continue ; // Change done val = 1 + countMinimalReplacements(s, i + 1, cur, dp, n); ans = min(ans, val); } } else // If same no change ans = countMinimalReplacements(s, i + 1, val, dp, n); return dp[i][val] = ans; } // Driver Code int main() { string s = "201220211" ; // Length of string int n = s.length(); // Create a DP array int dp[n][3]; memset (dp, -1, sizeof dp); // First character int val = charVal(s, 0); // Function to find minimal replacements cout << countMinimalReplacements(s, 1, val, dp, n); return 0; } |
Java
// Java program to count the minimal // replacements such that adjacent characters // are unequal class GFG { // function to return integer value // of i-th character in the string static int charVal(String s, int i) { if (s.charAt(i) == '0' ) { return 0 ; } else if (s.charAt(i) == '1' ) { return 1 ; } else { return 2 ; } } // Function to count the number of // minimal replacements static int countMinimalReplacements(String s, int i, int prev, int dp[][], int n) { // If the string has reached the end if (i == n) { return 0 ; } // If the state has been visited previously if (dp[i][prev] != - 1 ) { return dp[i][prev]; } // Get the current value of character int val = charVal(s, i); int ans = Integer.MAX_VALUE; // If it is equal then change it if (val == prev) { val = 0 ; // All possible changes for ( int cur = 0 ; cur <= 2 ; cur++) { if (cur == prev) { continue ; } // Change done val = 1 + countMinimalReplacements(s, i + 1 , cur, dp, n); ans = Math.min(ans, val); } } else // If same no change { ans = countMinimalReplacements(s, i + 1 , val, dp, n); } return dp[i][val] = ans; } // Driver Code public static void main(String[] args) { String s = "201220211" ; // Length of string int n = s.length(); // Create a DP array int dp[][] = new int [n][ 3 ]; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < 3 ; j++) { dp[i][j] = - 1 ; } } // First character int val = charVal(s, 0 ); // Function to find minimal replacements System.out.println(countMinimalReplacements(s, 1 , val, dp, n)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python 3 program to count the minimal # replacements such that adjacent characters # are unequal import sys # function to return integer value # of i-th character in the string def charVal(s, i): if (s[i] = = '0' ): return 0 elif (s[i] = = '1' ): return 1 else : return 2 # Function to count the number of # minimal replacements def countMinimalReplacements(s,i,prev, dp, n): # If the string has reached the end if (i = = n): return 0 # If the state has been visited previously if (dp[i][prev] ! = - 1 ): return dp[i][prev] # Get the current value of character val = charVal(s, i) ans = sys.maxsize # If it is equal then change it if (val = = prev): val = 0 # All possible changes for cur in range ( 3 ): if (cur = = prev): continue # Change done val = 1 + countMinimalReplacements(s, i + 1 , cur, dp, n) ans = min (ans, val) # If same no change else : ans = countMinimalReplacements(s, i + 1 , val, dp, n) dp[i][val] = ans return dp[i][val] # Driver Code if __name__ = = '__main__' : s = "201220211" # Length of string n = len (s) # Create a DP array dp = [[ - 1 for i in range ( 3 )] for i in range (n)] # First character val = charVal(s, 0 ) # Function to find minimal replacements print (countMinimalReplacements(s, 1 , val, dp, n)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to count the minimal // replacements such that adjacent // characters are unequal using System; class GFG { // function to return integer value // of i-th character in the string static int charVal( string s, int i) { if (s[i] == '0' ) { return 0; } else if (s[i] == '1' ) { return 1; } else { return 2; } } // Function to count the number of // minimal replacements static int countMinimalReplacements( string s, int i, int prev, int [,]dp, int n) { // If the string has reached the end if (i == n) { return 0; } // If the state has been visited previously if (dp[i,prev] != -1) { return dp[i,prev]; } // Get the current value of character int val = charVal(s, i); int ans = int .MaxValue; // If it is equal then change it if (val == prev) { val = 0; // All possible changes for ( int cur = 0; cur <= 2; cur++) { if (cur == prev) { continue ; } // Change done val = 1 + countMinimalReplacements(s, i + 1, cur, dp, n); ans = Math.Min(ans, val); } } else // If same no change { ans = countMinimalReplacements(s, i + 1, val, dp, n); } return dp[i,val] = ans; } // Driver Code public static void Main() { string s = "201220211" ; // Length of string int n = s.Length; // Create a DP array int [,]dp = new int [n,3]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < 3; j++) { dp[i,j] = -1; } } // First character int val = charVal(s, 0); // Function to find minimal replacements Console.WriteLine(countMinimalReplacements(s, 1, val, dp, n)); } } // This code is contributed by Ryuga |
Javascript
<script> // JavaScript 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 charVal( s , i) { if (s.charAt(i) == '0' ) { return 0; } else if (s.charAt(i) == '1' ) { return 1; } else { return 2; } } // Function to count the number of // minimal replacements function countMinimalReplacements( s , i , prev , dp , n) { // If the string has reached the end if (i == n) { return 0; } // If the state has been visited previously if (dp[i][prev] != -1) { return dp[i][prev]; } // Get the current value of character var val = charVal(s, i); var ans = Number.MAX_VALUE; // If it is equal then change it if (val == prev) { val = 0; // All possible changes for ( var cur = 0; cur <= 2; cur++) { if (cur == prev) { continue ; } // Change done val = 1 + countMinimalReplacements(s, i + 1, cur, dp, n); ans = Math.min(ans, val); } } else // If same no change { ans = countMinimalReplacements(s, i + 1, val, dp, n); } return dp[i][val] = ans; } // Driver Code var s = "201220211" ; // Length of string var n = s.length; // Create a DP array var dp = Array(n).fill().map(()=>Array(3).fill(0)); for ( var i = 0; i < n; i++) { for ( var j = 0; j < 3; j++) { dp[i][j] = -1; } } // First character var val = charVal(s, 0); // Function to find minimal replacements document.write(countMinimalReplacements(s, 1, val, dp, n)); // This code contributed by Rajput-Ji </script> |
2
Complexity Analysis:
- Time Complexity: O(3*N), as we are using recursion with memoization will cost us O(N) time as we will avoid unnecessary recursive calls. Where N is the number of characters in the string.
- Auxiliary Space: O(3*N), as we are using extra space for the DP matrix. Where N is the number of characters in the string.
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases dp[0][val] = 0.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Create variable ans to store final result and initialize it with INT_MAX.
- Now iterate over DP and update ans.
- At last return and print ans.
Implementation :
C++
// C++ program to count the minimal // replacements such that adjacent characters // are unequal #include <bits/stdc++.h> using namespace std; // function to return integer value // of i-th character in the string int charVal(string s, int i) { if (s[i] == '0' ) return 0; else if (s[i] == '1' ) return 1; else return 2; } // Function to count the number of // minimal replacements int countMinimalReplacements(string s, int n) { // create DP int dp[n][3]; // initialize it with -1 memset (dp, -1, sizeof dp); int val = charVal(s, 0); // Base Case dp[0][val] = 0; // iterate over subproblems to get the // current value from previous computations for ( int i = 1; i < n; i++) { int curVal = charVal(s, i); for ( int prev = 0; prev <= 2; prev++) { // Update DP in different conditions if (dp[i-1][prev] == -1) continue ; if (curVal == prev) { for ( int cur = 0; cur <= 2; cur++) { if (cur == prev) continue ; int newVal = dp[i-1][prev] + 1; if (dp[i][cur] == -1 || newVal < dp[i][cur]) { dp[i][cur] = newVal; } } } else { int newVal = dp[i-1][prev]; if (dp[i][curVal] == -1 || newVal < dp[i][curVal]) { dp[i][curVal] = newVal; } } } } // to store final result int ans = INT_MAX; for ( int cur = 0; cur <= 2; cur++) { if (dp[n-1][cur] == -1) continue ; // update ans ans = min(ans, dp[n-1][cur]); } // return answer return ans; } // Driver Code int main() { string s = "201220211" ; int n = s.length(); // function call cout << countMinimalReplacements(s, n) << endl; return 0; } |
Java
import java.util.Arrays; public class MinimalReplacements { // function to return integer value // of i-th character in the string static int charVal(String s, int i) { if (s.charAt(i) == '0' ) return 0 ; else if (s.charAt(i) == '1' ) return 1 ; else return 2 ; } // Function to count the number of // minimal replacements static int countMinimalReplacements(String s, int n) { // create DP int [][] dp = new int [n][ 3 ]; // initialize it with -1 for ( int i = 0 ; i < n; i++) { Arrays.fill(dp[i], - 1 ); } int val = charVal(s, 0 ); // Base Case dp[ 0 ][val] = 0 ; // iterate over subproblems to get the // current value from previous computations for ( int i = 1 ; i < n; i++) { int curVal = charVal(s, i); for ( int prev = 0 ; prev <= 2 ; prev++) { // Update DP in different conditions if (dp[i- 1 ][prev] == - 1 ) continue ; if (curVal == prev) { for ( int cur = 0 ; cur <= 2 ; cur++) { if (cur == prev) continue ; int newVal = dp[i- 1 ][prev] + 1 ; if (dp[i][cur] == - 1 || newVal < dp[i][cur]) { dp[i][cur] = newVal; } } } else { int newVal = dp[i- 1 ][prev]; if (dp[i][curVal] == - 1 || newVal < dp[i][curVal]) { dp[i][curVal] = newVal; } } } } // to store the final result int ans = Integer.MAX_VALUE; for ( int cur = 0 ; cur <= 2 ; cur++) { if (dp[n- 1 ][cur] == - 1 ) continue ; // update ans ans = Math.min(ans, dp[n- 1 ][cur]); } // return answer return ans; } // Driver Code public static void main(String[] args) { String s = "201220211" ; int n = s.length(); // function call System.out.println(countMinimalReplacements(s, n)); } } |
Python
# Python program to count the minimal # replacements such that adjacent characters # are unequal import sys # function to return integer value # of i-th character in the string def charVal(s, i): if (s[i] = = '0' ): return 0 elif (s[i] = = '1' ): return 1 else : return 2 # Function to count the number of # minimal replacements def countMinimalReplacements(s, n): # create DP dp = [[ - 1 for i in range ( 3 )] for j in range (n)] val = charVal(s, 0 ) # Base Case dp[ 0 ][val] = 0 # iterate over subproblems to get the # current value from previous computations for i in range ( 1 , n): curVal = charVal(s, i) for prev in range ( 0 , 3 ): # Update DP in different conditions if (dp[i - 1 ][prev] = = - 1 ): continue if (curVal = = prev): for cur in range ( 0 , 3 ): if (cur = = prev): continue newVal = dp[i - 1 ][prev] + 1 if (dp[i][cur] = = - 1 or newVal < dp[i][cur]): dp[i][cur] = newVal else : newVal = dp[i - 1 ][prev] if (dp[i][curVal] = = - 1 or newVal < dp[i][curVal]): dp[i][curVal] = newVal # to store final result ans = sys.maxsize for cur in range ( 0 , 3 ): if (dp[n - 1 ][cur] = = - 1 ): continue # update ans ans = min (ans, dp[n - 1 ][cur]) # return answer return ans # Driver Code if __name__ = = '__main__' : s = "201220211" n = len (s) # function call print (countMinimalReplacements(s, n)) |
C#
using System; class Program { // Function to return integer value // of i-th character in the string static int CharVal( string s, int i) { if (s[i] == '0' ) return 0; else if (s[i] == '1' ) return 1; else return 2; } // Function to count the number of // minimal replacements static int CountMinimalReplacements( string s, int n) { // Create DP int [][] dp = new int [n][]; for ( int i = 0; i < n; i++) { dp[i] = new int [3]; for ( int j = 0; j < 3; j++) { dp[i][j] = -1; } } int val = CharVal(s, 0); // Base Case dp[0][val] = 0; // Iterate over subproblems to get the // current value from previous computations for ( int i = 1; i < n; i++) { int curVal = CharVal(s, i); for ( int prev = 0; prev < 3; prev++) { // Update DP in different conditions if (dp[i - 1][prev] == -1) continue ; if (curVal == prev) { for ( int cur = 0; cur < 3; cur++) { if (cur == prev) continue ; int newVal = dp[i - 1][prev] + 1; if (dp[i][cur] == -1 || newVal < dp[i][cur]) { dp[i][cur] = newVal; } } } else { int newVal = dp[i - 1][prev]; if (dp[i][curVal] == -1 || newVal < dp[i][curVal]) { dp[i][curVal] = newVal; } } } } // To store final result int ans = int .MaxValue; for ( int cur = 0; cur < 3; cur++) { if (dp[n - 1][cur] == -1) continue ; // Update ans ans = Math.Min(ans, dp[n - 1][cur]); } // Return answer return ans; } // Driver Code static void Main() { string s = "201220211" ; int n = s.Length; // Function call Console.WriteLine(CountMinimalReplacements(s, n)); } } |
Javascript
// Function to return the integer value // of i-th character in the string function charVal(s, i) { if (s[i] === '0' ) { return 0; } else if (s[i] === '1' ) { return 1; } else { return 2; } } // Function to count the number of minimal replacements function countMinimalReplacements(s) { const n = s.length; // Create a DP array and initialize it with -1 const dp = new Array(n); for (let i = 0; i < n; i++) { dp[i] = new Array(3).fill(-1); } const val = charVal(s, 0); // Base Case dp[0][val] = 0; // Iterate over subproblems to get the current value from previous computations for (let i = 1; i < n; i++) { const curVal = charVal(s, i); for (let prev = 0; prev <= 2; prev++) { // Update DP in different conditions if (dp[i-1][prev] === -1) continue ; if (curVal === prev) { for (let cur = 0; cur <= 2; cur++) { if (cur === prev) continue ; const newVal = dp[i-1][prev] + 1; if (dp[i][cur] === -1 || newVal < dp[i][cur]) { dp[i][cur] = newVal; } } } else { const newVal = dp[i-1][prev]; if (dp[i][curVal] === -1 || newVal < dp[i][curVal]) { dp[i][curVal] = newVal; } } } } // To store the final result let ans = Infinity; for (let cur = 0; cur <= 2; cur++) { if (dp[n-1][cur] === -1) continue ; // Update ans ans = Math.min(ans, dp[n-1][cur]); } // Return the answer return ans; } // Driver Code const s = "201220211" ; const n = s.length; // Function call console.log(countMinimalReplacements(s)); |
Output:
2
Time Complexity: O(3*N)
Auxiliary Space: O(3*N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!