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 stringint 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 replacementsint 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 Codeint 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 unequalclass 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 unequalimport sys# function to return integer value# of i-th character in the stringdef 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 replacementsdef 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 Codeif __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 unequalusing 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> |
Output
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 stringint 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 replacementsint 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 Codeint 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 unequalimport sys# function to return integer value# of i-th character in the stringdef 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 replacementsdef 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 Codeif __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)); }} |
Output:
2
Time Complexity: O(3*N)
Auxiliary Space: O(3*N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
