Given a string consisting of only three possible characters ‘a’, ‘b’ or ‘c’. The task is to replace characters of the given string with ‘a’, ‘b’ or ‘c’ only such that there is the equal number of characters of ‘a’, ‘b’ and ‘c’ in the string. The task is to minimize the number of replacements and print the lexicographically smallest string possible of all such strings with minimal replacements. If it is not possible to obtain such a string, print -1. Examples:
Input : s = "bcabba" Output : bcabca Number of replacements done is 1 and this is the lexicographically smallest possible Input : "aaaaaa" Output : aabbcc Input : "aaaaa" Output : -1
Approach:
- Count the number of ‘a’, ‘b’ and ‘c’ in the string.
- If the count of them is equal then the same string will be the answer.
- If length of the string is not a multiple of 3, then it is not possible.
- First, reduce the number of exceeding a’s in the string.
- Replace ‘c’ by ‘a’ if there are extra ‘c’ using a sliding window technique from left.
- Replace ‘b’ by ‘a’ if there are extra ‘b’ using a sliding window technique from left in case of no ‘c’ at an index.
- Secondly, reduce the number of exceeding b’s in the string by replacing ‘c’ from front using sliding window.
- Thirdly, reduce the number of exceeding c’s by reducing the number of extra ‘a’ from the back using sliding window.
- Fourthly, reduce the number of exceeding b’s in the string by reducing the number of extra ‘a’ from the back.
- Fifthly, reduce the number of exceeding c’s if any by reducing the number of extra ‘b’ from the back.
We keep on replacing from back in order to get the lexicographically smallest string. Below is the implementation of the above approach:
C++
// CPP program to Minimize the number of // replacements to get a string with same // number of ‘a’, ‘b’ and ‘c’ in it #include <bits/stdc++.h> using namespace std; // Function to count numbers string lexoSmallest(string s, int n) { // Count the number of 'a', 'b' and // 'c' in string int ca = 0, cb = 0, cc = 0; for ( int i = 0; i < n; i++) { if (s[i] == 'a' ) ca++; else if (s[i] == 'b' ) cb++; else cc++; } // If equal previously if (ca == cb && cb == cc) { return s; } int cnt = n / 3; // If not a multiple of 3 if (cnt * 3 != n) { return "-1" ; } int i = 0; // Increase the number of a's by // removing extra 'b' and ;c; while (ca < cnt && i < n) { // Check if it is 'b' and it more // than n/3 if (s[i] == 'b' && cb > cnt) { cb--; s[i] = 'a' ; ca++; } // Check if it is 'c' and it // more than n/3 else if (s[i] == 'c' && cc > cnt) { cc--; s[i] = 'a' ; ca++; } i++; } i = 0; // Increase the number of b's by // removing extra 'c' while (cb < cnt && i < n) { // Check if it is 'c' and it more // than n/3 if (s[i] == 'c' && cc > cnt) { cc--; s[i] = '1' ; cb++; } i++; } i = n - 1; // Increase the number of c's from back while (cc < cnt && i >= 0) { // Check if it is 'a' and it more // than n/3 if (s[i] == 'a' && ca > cnt) { ca--; s[i] = 'c' ; cc++; } i--; } i = n - 1; // Increase the number of b's from back while (cb < cnt && i >= 0) { // Check if it is 'a' and it more // than n/3 if (s[i] == 'a' && ca > cnt) { ca--; s[i] = 'b' ; cb++; } i--; } i = n - 1; // Increase the number of c's from back while (cc < cnt && i >= 0) { // Check if it is 'b' and it more // than n/3 if (s[i] == 'b' && cb > cnt) { cb--; s[i] = 'c' ; cc++; } i--; } return s; } // Driver Code int main() { string s = "aaaaaa" ; int n = s.size(); cout << lexoSmallest(s, n); return 0; } |
Java
// Java program to minimize the number of // replacements to get a string with same // number of ‘a’, ‘b’ and ‘c’ in it import java.util.*; public class GFG { // Function to count numbers static String lexoSmallest(String str, int n) { // Count the number of 'a', 'b' and // 'c' in string int ca = 0 , cb = 0 , cc = 0 ; StringBuilder s = new StringBuilder(str); for ( int j = 0 ; j < n; j++) { if (s.charAt(j) == 'a' ) ca++; else if (s.charAt(j) == 'b' ) cb++; else cc++; } // If equal previously if (ca == cb && cb == cc) { return s.toString(); } int cnt = n / 3 ; // If not a multiple of 3 if (cnt * 3 != n) { return "-1" ; } int i = 0 ; // Increase the number of a's by // removing extra 'b' and ;c; while (ca < cnt && i < n) { // Check if it is 'b' and it more // than n/3 if (s.charAt(i) == 'b' && cb > cnt) { cb--; s.setCharAt(i, 'a' ); ca++; } // Check if it is 'c' and it // more than n/3 else if (s.charAt(i) == 'c' && cc > cnt) { cc--; s.setCharAt(i, 'a' ); ca++; } i++; } i = 0 ; // Increase the number of b's by // removing extra 'c' while (cb < cnt && i < n) { // Check if it is 'c' and it more // than n/3 if (s.charAt(i) == 'c' && cc > cnt) { cc--; s.setCharAt(i, '1' ); cb++; } i++; } i = n - 1 ; // Increase the number of c's from back while (cc < cnt && i >= 0 ) { // Check if it is 'a' and it more // than n/3 if (s.charAt(i) == 'a' && ca > cnt) { ca--; s.setCharAt(i, 'c' ); cc++; } i--; } i = n - 1 ; // Increase the number of b's from back while (cb < cnt && i >= 0 ) { // Check if it is 'a' and it more // than n/3 if (s.charAt(i) == 'a' && ca > cnt) { ca--; s.setCharAt(i, 'b' ); cb++; } i--; } i = n - 1 ; // Increase the number of c's from back while (cc < cnt && i >= 0 ) { // Check if it is 'b' and it more // than n/3 if (s.charAt(i) == 'b' && cb > cnt) { cb--; s.setCharAt(i, 'c' ); cc++; } i--; } return s.toString(); } // Driver Code public static void main(String[] args) { String s = "aaaaaa" ; int n = s.length(); System.out.println(lexoSmallest(s, n)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 program to Minimize the number of # replacements to get a string with same # number of 'a', 'b' and 'c' in it # Function to count numbers def lexoSmallest(s, n): # Count the number of 'a', 'b' and # 'c' in string ca = 0 cb = 0 cc = 0 for i in range (n): if (s[i] = = 'a' ): ca + = 1 elif (s[i] = = 'b' ): cb + = 1 else : cc + = 1 # If equal previously if (ca = = cb and cb = = cc): return s cnt = n / / 3 # If not a multiple of 3 if (cnt * 3 ! = n): return "-1" i = 0 # Increase the number of a's by # removing extra 'b' and c while (ca < cnt and i < n): # Check if it is 'b' and it more # than n/3 if (s[i] = = 'b' and cb > cnt) : cb - = 1 s[i] = 'a' ca + = 1 # Check if it is 'c' and it # more than n/3 elif (s[i] = = 'c' and cc > cnt): cc - = 1 s[i] = 'a' ca + = 1 i + = 1 i = 0 # Increase the number of b's by # removing extra 'c' while (cb < cnt and i < n): # Check if it is 'c' and it more # than n/3 if (s[i] = = 'c' and cc > cnt): cc - = 1 s[i] = '1' cb + = 1 i + = 1 i = n - 1 # Increase the number of c's from back while (cc < cnt and i > = 0 ): # Check if it is 'a' and it more # than n/3 if (s[i] = = 'a' and ca > cnt): ca - = 1 s[i] = 'c' cc + = 1 i - = 1 i = n - 1 # Increase the number of b's from back while (cb < cnt and i > = 0 ): # Check if it is 'a' and it more # than n/3 if (s[i] = = 'a' and ca > cnt): ca - = 1 s[i] = 'b' cb + = 1 i - = 1 i = n - 1 # Increase the number of c's from back while (cc < cnt and i > = 0 ): # Check if it is 'b' and it more # than n/3 if (s[i] = = 'b' and cb > cnt): cb - = 1 s[i] = 'c' cc + = 1 i - = 1 return s # Driver Code s = "aaaaaa" n = len (s) print ( * lexoSmallest( list (s), n),sep = "") # This code is contributed by shivanisinghss2110 |
C#
// C# program to minimize the number of // replacements to get a string with same // number of ‘a’, ‘b’ and ‘c’ in it using System; using System.Text; class GFG{ // Function to count numbers static string lexoSmallest( string str, int n) { // Count the number of 'a', 'b' and // 'c' in string int ca = 0, cb = 0, cc = 0; StringBuilder s = new StringBuilder(str); for ( int j = 0; j < n; j++) { if (s[j] == 'a' ) ca++; else if (s[j] == 'b' ) cb++; else cc++; } // If equal previously if (ca == cb && cb == cc) { return s.ToString(); } int cnt = n / 3; // If not a multiple of 3 if (cnt * 3 != n) { return "-1" ; } int i = 0; // Increase the number of a's by // removing extra 'b' and ;c; while (ca < cnt && i < n) { // Check if it is 'b' and it more // than n/3 if (s[i] == 'b' && cb > cnt) { cb--; s[i] = 'a' ; ca++; } // Check if it is 'c' and it // more than n/3 else if (s[i] == 'c' && cc > cnt) { cc--; s[i] = 'a' ; ca++; } i++; } i = 0; // Increase the number of b's by // removing extra 'c' while (cb < cnt && i < n) { // Check if it is 'c' and it more // than n/3 if (s[i] == 'c' && cc > cnt) { cc--; s[i] = '1' ; cb++; } i++; } i = n - 1; // Increase the number of c's from back while (cc < cnt && i >= 0) { // Check if it is 'a' and it more // than n/3 if (s[i] == 'a' && ca > cnt) { ca--; s[i] = 'c' ; cc++; } i--; } i = n - 1; // Increase the number of b's from back while (cb < cnt && i >= 0) { // Check if it is 'a' and it more // than n/3 if (s[i] == 'a' && ca > cnt) { ca--; s[i] = 'b' ; cb++; } i--; } i = n - 1; // Increase the number of c's from back while (cc < cnt && i >= 0) { // Check if it is 'b' and it more // than n/3 if (s[i] == 'b' && cb > cnt) { cb--; s[i] = 'c' ; cc++; } i--; } return s.ToString(); } // Driver Code public static void Main( string [] args) { string s = "aaaaaa" ; int n = s.Length; Console.Write(lexoSmallest(s, n)); } } // This code is contributed by rutvik_56 |
PHP
<?php // PHP program to Minimize the number of // replacements to get a string with same // number of ‘a’, ‘b’ and ‘c’ in it // Function to count numbers function lexoSmallest( $s , $n ) { // Count the number of 'a', 'b' // and 'c' in string $ca = 0; $cb = 0; $cc = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $s [ $i ] == 'a' ) $ca ++; else if ( $s [ $i ] == 'b' ) $cb ++; else $cc ++; } // If equal previously if ( $ca == $cb && $cb == $cc ) { return $s ; } $cnt = floor ( $n / 3); // If not a multiple of 3 if ( $cnt * 3 != $n ) { return "-1" ; } $i = 0; // Increase the number of a's by // removing extra 'b' and ;c; while ( $ca < $cnt && $i < $n ) { // Check if it is 'b' and it is // more than n/3 if ( $s [ $i ] == 'b' && $cb > $cnt ) { $cb --; $s [ $i ] = 'a' ; $ca ++; } // Check if it is 'c' and it // more than n/3 else if ( $s [ $i ] == 'c' && $cc > $cnt ) { $cc --; $s [ $i ] = 'a' ; $ca ++; } $i ++; } $i = 0; // Increase the number of b's by // removing extra 'c' while ( $cb < $cnt && $i < $n ) { // Check if it is 'c' and it more // than n/3 if ( $s [ $i ] == 'c' && $cc > $cnt ) { $cc --; $s [ $i ] = '1' ; $cb ++; } $i ++; } $i = $n - 1; // Increase the number of c's from back while ( $cc < $cnt && $i >= 0) { // Check if it is 'a' and it is // more than n/3 if ( $s [ $i ] == 'a' && $ca > $cnt ) { $ca --; $s [ $i ] = 'c' ; $cc ++; } $i --; } $i = $n - 1; // Increase the number of b's from back while ( $cb < $cnt && $i >= 0) { // Check if it is 'a' and it is // more than n/3 if ( $s [ $i ] == 'a' && $ca > $cnt ) { $ca --; $s [ $i ] = 'b' ; $cb ++; } $i --; } $i = $n - 1; // Increase the number of c's from back while ( $cc < $cnt && $i >= 0) { // Check if it is 'b' and it more // than n/3 if ( $s [ $i ] == 'b' && $cb > $cnt ) { $cb --; $s [ $i ] = 'c' ; $cc ++; } $i --; } return $s ; } // Driver Code $s = "aaaaaa" ; $n = strlen ( $s ); echo lexoSmallest( $s , $n ); // This code is contributed by Ryuga. ?> |
Javascript
// Javascript program to Minimize the number of // replacements to get a string with same // number of ‘a’, ‘b’ and ‘c’ in it // Utility code for replacing a character // at a specified index function setCharAt(str,index,chr) { if (index > str.length-1) { return str; } return str.substring(0,index) + chr + str.substring(index+1); } // Function to count numbers function lexoSmallest(s, n) { // Count the number of 'a', 'b' and // 'c' in string let ca = 0, cb = 0, cc = 0; for (let i = 0; i < n; i++) { if (s[i] == 'a' ) ca++; else if (s[i] == 'b' ) cb++; else cc++; } // If equal previously if (ca == cb && cb == cc) { return s; } let cnt = n / 3; // If not a multiple of 3 if (cnt * 3 != n) { return "-1" ; } let i = 0; // Increase the number of a's by // removing extra 'b' and ;c; while (ca < cnt && i < n) { // Check if it is 'b' and it more // than n/3 if (s[i] == 'b ' && cb > cnt) { cb--; s = setCharAt(s, i, ' a '); ca++; } // Check if it is ' c ' and it // more than n/3 else if (s[i] == ' c ' && cc > cnt) { cc--; s = setCharAt(s, i, ' a '); ca++; } i++; } i = 0; // Increase the number of b' s by // removing extra 'c' while (cb < cnt && i < n) { // Check if it is 'c' and it more // than n/3 if (s[i] == 'c' && cc > cnt) { cc--; s = setCharAt(s, i, '1' ); cb++; } i++; } i = n - 1; // Increase the number of c's from back while (cc < cnt && i >= 0) { // Check if it is 'a' and it more // than n/3 if (s[i] == 'a ' && ca > cnt) { ca--; s = setCharAt(s, i, ' c '); cc++; } i--; } i = n - 1; // Increase the number of b' s from back while (cb < cnt && i >= 0) { // Check if it is 'a' and it more // than n/3 if (s[i] == 'a' && ca > cnt) { ca--; s = setCharAt(s, i, 'b' ); cb++; } i--; } i = n - 1; // Increase the number of c's from back while (cc < cnt && i >= 0) { // Check if it is 'b' and it more // than n/3 if (s[i] == 'b ' && cb > cnt) { cb--; s = setCharAt(s, i, ' c'); cc++; } i--; } return s; } // Driver Code let s = "aaaaaa" ; let n = s.length; console.log(lexoSmallest(s, n)); // This code is contributed by Samim Hossain Mondal. |
aabbcc
Time Complexity: O(N*6)
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!