Minimum replacements to make adjacent characters unequal in a ternary string
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 following problem can be solved using the greedy method. We can greedily compare every adjacent pair. If the adjacent pairs which are characters at ith and i-1th are the same, then replace the ith character with a character that is not equal to the character at i-1th and i+1th index. In the case of the last adjacent pair, just replace it with the character which is not equal to the character at the i-1th index.
Below is the implementation of the above approach:
C++
// C++ program to count the minimal // replacements such that adjacent characters // are unequal #include <bits/stdc++.h> using namespace std; // Function to count the number of // minimal replacements int countMinimalReplacements(string s) { // Find the length of the string int n = s.length(); int cnt = 0; // Iterate in the string for ( int i = 1; i < n; i++) { // Check if adjacent is similar if (s[i] == s[i - 1]) { cnt += 1; // If not the last pair if (i != (n - 1)) { // Check for character which is // not same in i+1 and i-1 for ( auto it : "012" ) { if (it != s[i + 1] && it != s[i - 1]) { s[i] = it; break ; } } } else // Last pair { // Check for character which is // not same in i-1 index for ( auto it : "012" ) { if (it != s[i - 1]) { s[i] = it; break ; } } } } } return cnt; } // Driver Code int main() { string s = "201220211" ; cout << countMinimalReplacements(s); return 0; } |
Java
// Java program to count the minimal // replacements such that adjacent // characters are unequal class GFG { static final int MAX = 26 ; // Function to count the number of // minimal replacements static int countMinimalReplacements( char [] s) { // Find the length of the String int n = s.length; int cnt = 0 ; // Iterate in the String for ( int i = 1 ; i < n; i++) { // Check if adjacent is similar if (s[i] == s[i - 1 ]) { cnt += 1 ; // If not the last pair if (i != (n - 1 )) { // Check for character which is // not same in i+1 and i-1 for ( char it : "012" .toCharArray()) { if (it != s[i + 1 ] && it != s[i - 1 ]) { s[i] = it; break ; } } } else // Last pair { // Check for character which is // not same in i-1 index for ( char it : "012" .toCharArray()) { if (it != s[i - 1 ]) { s[i] = it; break ; } } } } } return cnt; } // Driver Code public static void main(String[] args) { String s = "201220211" ; System.out.println(countMinimalReplacements(s.toCharArray())); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program to count the minimal # replacements such that adjacent # characters are unequal # Function to count the number of # minimal replacements def countMinimalReplacements(s): # Find the length of the string n = len (s) cnt = 0 # Iterate in the string for i in range ( 1 , n): # Check if adjacent is similar if (s[i] = = s[i - 1 ]): cnt + = 1 ; # If not the last pair if (i ! = (n - 1 )): # Check for character which is # not same in i+1 and i-1 s = list (s) for j in "012" : if (j ! = s[i + 1 ] and j ! = s[i - 1 ]): s[i] = j break s = ''.join(s) # Last pair else : # Check for character which is # not same in i-1 index s = list (s) for k in "012" : if (k ! = s[i - 1 ]): s[i] = k break s = ''.join(s) return cnt # Driver Code if __name__ = = '__main__' : s = "201220211" print (countMinimalReplacements(s)) # 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 { static readonly int MAX = 26; // Function to count the number of // minimal replacements static int countMinimalReplacements( char [] s) { // Find the length of the String int n = s.Length; int cnt = 0; // Iterate in the String for ( int i = 1; i < n; i++) { // Check if adjacent is similar if (s[i] == s[i - 1]) { cnt += 1; // If not the last pair if (i != (n - 1)) { // Check for character which is // not same in i+1 and i-1 foreach ( char it in "012" .ToCharArray()) { if (it != s[i + 1] && it != s[i - 1]) { s[i] = it; break ; } } } else // Last pair { // Check for character which is // not same in i-1 index foreach ( char it in "012" .ToCharArray()) { if (it != s[i - 1]) { s[i] = it; break ; } } } } } return cnt; } // Driver Code public static void Main(String[] args) { String s = "201220211" ; Console.WriteLine(countMinimalReplacements(s.ToCharArray())); } } // This code is contributed by Rajput-Ji |
PHP
<?php // PHP program to count the minimal // replacements such that adjacent // characters are unequal // Function to count the number of // minimal replacements function countMinimalReplacements( $s ) { // Find the length of the string $n = strlen ( $s ); $cnt = 0; $str = "012" ; // Iterate in the string for ( $i = 1; $i < $n ; $i ++) { // Check if adjacent is similar if ( $s [ $i ] == $s [ $i - 1]) { $cnt += 1; // If not the last pair if ( $i != ( $n - 1)) { // Check for character which is // not same in i+1 and i-1 for ( $it = 0 ; $it < strlen ( $str ); $it ++) { if ( $str [ $it ] != $s [ $i + 1] && $str [ $it ] != $s [ $i - 1]) { $s [ $i ] = $str [ $it ]; break ; } } } else // Last pair { // Check for character which is // not same in i-1 index for ( $it = 0 ; $it < strlen ( $str ); $it ++) { if ( $str [ $it ] != $s [ $i - 1]) { $s [ $i ] = $str [ $it ]; break ; } } } } } return $cnt ; } // Driver Code $s = "201220211" ; echo countMinimalReplacements( $s ); // This code is contributed by Ryuga ?> |
Javascript
<script> // JavaScript program to count the minimal // replacements such that adjacent // characters are unequal // Function to count the number of // minimal replacements function countMinimalReplacements(s) { // Find the length of the string var n = s.length; var cnt = 0; var str = "012" ; // Iterate in the string for ( var i = 1; i < n; i++) { // Check if adjacent is similar if (s[i] === s[i - 1]) { cnt += 1; // If not the last pair if (i !== n - 1) { // Check for character which is // not same in i+1 and i-1 for ( var it = 0; it < str.length; it++) { if (str[it] !== s[i + 1] && str[it] !== s[i - 1]) { s[i] = str[it]; break ; } } } // Last pair else { // Check for character which is // not same in i-1 index for ( var it = 0; it < str.length; it++) { if (str[it] !== s[i - 1]) { s[i] = str[it]; break ; } } } } } return cnt; } // Driver Code var s = "201220211" ; document.write(countMinimalReplacements(s)); </script> |
2
Complexity Analysis:
- Time Complexity: O(3*n), as we are using a loop to traverse n times. Where n is the number of elements in the array.
- Auxiliary Space: O(1), as we are not using any extra space.
Contact Us