Given string str of length N and a character X, where N is always of the form 2k, the task is to find the minimum replacement operations required to reduce the size of the string to 1 wherein ith deletion, N/2i occurrences of (X + i – 1)th character can be deleted either from the front or the back of the string.
Example:
Input: str = “CDAAAABB”, X = ‘A’
Output: 4
Explanation: Replacement operations on the given string can be done as:
- Replace ‘C’ at 1st index with ‘A’.
- Replace ‘D’ at 2nd index with ‘A’.
- Replace ‘A’ at 5th index with ‘D’.
- Replace ‘A’ at 6th index with ‘C’.
Therefore, the string becomes str = “AAAADCBB”. During the 1st deletion (8/21) occurrences of (A+1-1)th character can be removed from the front of the string. Therefore, the string becomes str = “DCBB”. Similarly, during the 2nd deletion (8/22) occurrences of (A+2-1)th i.e, ‘B’ character can be removed from the back of the string. Therefore, the string becomes str = “DC”. Similarly, after the 3rd deletion, the string becomes str = “D” having length as 1. Therefore, the number of required replacement operations are 4 which is the minimum possible.
Input: str = “QRQP”, X = ‘P’
Output: 1
Approach: The given problem can be solved by using Recursion having a similar structure as that of the Binary Search. During each deletion, it can be observed that there are 2 possible choices. They are as follows:
- Replace all the characters of the first half of the given string by ‘X’ and recursively call for the remaining half for X = X + 1.
- Or, replace all the characters of the second half of the given string by ‘X’ and recursively call for the remaining half for X = X + 1.
Therefore, using the above observations create a recursive function that takes the minimum moves out of the two possibilities by calculating the number of indices that need to be replaced to X in the first half of the string and recursively calling for the remaining half and vice versa.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to find minimum// replacements required to reduce the// size of the given string to 1int minReplacment(string s, char x){ // Base Case if (s.size() == 1) { return s[0] != x; } // Stores the middle index int mid = s.size() / 2; // Recursive call for left half int cntl = minReplacment( string(s.begin(), s.begin() + mid), x + 1); cntl += s.size() / 2 - count(s.begin() + mid, s.end(), x); // Recursive call for right half int cntr = minReplacment( string(s.begin() + mid, s.end()), x + 1); cntr += s.size() / 2 - count(s.begin(), s.begin() + mid, x); // Return Answer return min(cntl, cntr);}// Driver Codeint main(){ int N = 8; string str = "CDAAAABB"; char X = 'A'; cout << minReplacment(str, X); return 0;} |
Java
/*package whatever //do not write package name here */// Java code for the above approachimport java.util.*;class GFG { public static int count(String str, char c) { int ct = 0; for (int i = 0; i < str.length(); i++) { char currChar = str.charAt(i); if (currChar == c) ct += 1; } return ct; } // Recursive function to find minimum // replacements required to reduce the // size of the given string to 1 static int minReplacment(String s, char x) { // Base Case if (s.length() == 1) { if (s.charAt(0) == x) return 1; return 0; } // Stores the middle index int mid = s.length() / 2; // Recursive call for left half char p = (char)(x + 1); int cntl = minReplacment(s.substring(0, mid), p); cntl = cntl + s.length() / 2 - count(s.substring(mid, s.length()), x); // Recursive call for right half char t = (char)(x + 1); int cntr = minReplacment( s.substring(mid, s.length()), t); cntr = cntr + s.length() / 2 - count(s.substring(0, mid), x); // Return Answer return Math.min(cntl + 1, cntr); } // Driver Code public static void main(String[] args) { int N = 8; String str = "CDAAAABB"; char X = 'A'; System.out.println(minReplacment(str, X)); }}// This code is contributed by Potta Lokesh |
Python3
# Python 3 implementation for the above approach# Recursive function to find minimum# replacements required to reduce the# size of the given string to 1def minReplacment(s, x): # Base Case if (len(s) == 1): return s[0] != x # Stores the middle index mid = len(s) // 2 # Recursive call for left half cntl = minReplacment( s[:mid], chr(ord(x) + 1)) cntl += len(s) // 2 - s[mid:].count(x) # Recursive call for right half cntr = minReplacment( s[mid:], chr(ord(x) + 1)) cntr += len(s) // 2 - s[:mid].count(x) # Return Answer return min(cntl, cntr)# Driver Codeif __name__ == "__main__": N = 8 st = "CDAAAABB" X = 'A' print(minReplacment(st, X)) # This code is contributed by ukasp. |
C#
/*package whatever //do not write package name here */// C# code for the above approachusing System;public class GFG { public static int count(String str, char c) { int ct = 0; for (int i = 0; i < str.Length; i++) { char currChar = str[i]; if (currChar == c) ct += 1; } return ct; } // Recursive function to find minimum // replacements required to reduce the // size of the given string to 1 static int minReplacment(String s, char x) { // Base Case if (s.Length == 1) { if (s[0] == x) return 1; return 0; } // Stores the middle index int mid = s.Length / 2; // Recursive call for left half char p = (char)(x + 1); int cntl = minReplacment(s.Substring(0, mid), p); cntl = cntl + s.Length / 2 - count(s.Substring(mid, s.Length-mid), x); // Recursive call for right half char t = (char)(x + 1); int cntr = minReplacment( s.Substring(mid, s.Length-mid), t); cntr = cntr + s.Length / 2 - count(s.Substring(0, mid), x); // Return Answer return Math.Min(cntl + 1, cntr); } // Driver Code public static void Main(String[] args) { String str = "CDAAAABB"; char X = 'A'; Console.WriteLine(minReplacment(str, X)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript implementation for the above approachfunction count(str, c) { let ct = 0; for (let i = 0; i < str.length; i++) { let currChar = str[i]; if (currChar == c) ct += 1; } return ct;}// Recursive function to find minimum// replacements required to reduce the// size of the given string to 1function minReplacment(s, x) { // Base Case if (s.length == 1) { if(s[0] == x){ return 1 } return 0 } // Stores the middle index let mid = Math.floor(s.length / 2); // Recursive call for left half let cntl = minReplacment(s.substring(0, mid), String.fromCharCode(x.charCodeAt(0) + 1)); cntl += Math.floor(s.length / 2) - count(s.substring(mid, s.length), x); // Recursive call for right half let cntr = minReplacment(new String(s.substring(mid, s.length)), String.fromCharCode(x.charCodeAt(0) + 1)); cntr += Math.floor(s.length / 2) - count(s.substring(0, mid), x); // Return Answer return Math.min(cntl + 1, cntr);}// Driver Codelet N = 8;let str = "CDAAAABB";let X = 'A';document.write(minReplacment(str, X));// This code is contributed by gfgking.</script> |
4
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
