Given string str, a character ch, and an integer K, the task is to find the minimum number of operations required to convert all the characters of string str to ch. Each operation involves converting K closest characters from each side of the index i, i.e., characters in the indices [i – K, i + K] can be converted to ch.
Note: Each index can be part of a single operation only.
Examples:
Input: str = “abcsdx”, K = 2, ch = ‘#’
Output: 2
Explanation:
Operation 1: Select i = 1, therefore, str = “abcsdx” modifies to “###sdx”.
Operation 2: Select i = 6, therefore, str = “###sdx” modifies to “######”.
Input: str = “Hellomypkfsg”, k = 3, ch = ‘$’
Output:2
Explanation:
Operation 1: Select i = 2, therefore, str = “Hellomypkfsg” modifies to “$$$$$mypkfsg”.
Operation 2: Select i = 9, therefore, str = “$$$$$mypkfsg” modifies to “$$$$$$$$$$$$”.
Approach:
Follow the steps below to solve the problem:
- For any index i, the maximum number of characters that can be converted is 2 * K + 1. Therefore, if the total number of characters in the string does not exceed 2 * K, a single operation is required only to convert the entire string into ch.
- Otherwise, the number of operations required will be ceil(n / (2*k+1)).
- Iterate over the string, starting from the leftmost possible index that can be used for the operation, and print every (2*k+1)th index after it.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum// number of operations requiredvoid countOperations(int n, int k){ // Maximum number of characters that // can be changed in one operation int div = 2 * k + 1; // If length of the string less than // maximum number of characters that // can be changed in an operation if (n / 2 <= k) { cout << 1 << "\n"; // Set the last index as the // index for the operation if (n > k) cout << k + 1; else cout << n; } // Otherwise else { // If size of the string is // equal to the maximum number // of characters in an operation if (n % div == 0) { // Find the number of // operations required int oprn = n / div; cout << oprn << "\n"; // Find the starting position int pos = k + 1; cout << pos << " "; for (int i = 1; i <= oprn; i++) { // Print i-th index cout << pos << " "; // Shift to next index pos += div; } } // Otherwise else { // Find the number of // operations required int oprn = n / div + 1; cout << oprn << "\n"; int pos = n % div; // If n % div exceeds k if (n % div > k) pos -= k; for (int i = 1; i <= oprn; i++) { // Print i-th index cout << pos << " "; // Shift to next index pos += div; } } }}// Driver Codeint main(){ string str = "edfreqwsazxet"; char ch = '$'; int n = str.size(); int k = 4; countOperations(n, k); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function to find the minimum// number of operations requiredstatic void countOperations(int n, int k){ // Maximum number of characters that // can be changed in one operation int div = 2 * k + 1; // If length of the String less than // maximum number of characters that // can be changed in an operation if (n / 2 <= k) { System.out.print(1 + "\n"); // Set the last index as the // index for the operation if (n > k) System.out.print(k + 1); else System.out.print(n); } // Otherwise else { // If size of the String is // equal to the maximum number // of characters in an operation if (n % div == 0) { // Find the number of // operations required int oprn = n / div; System.out.print(oprn + "\n"); // Find the starting position int pos = k + 1; System.out.print(pos + " "); for(int i = 1; i <= oprn; i++) { // Print i-th index System.out.print(pos + " "); // Shift to next index pos += div; } } // Otherwise else { // Find the number of // operations required int oprn = n / div + 1; System.out.print(oprn + "\n"); int pos = n % div; // If n % div exceeds k if (n % div > k) pos -= k; for(int i = 1; i <= oprn; i++) { // Print i-th index System.out.print(pos + " "); // Shift to next index pos += div; } } }}// Driver Codepublic static void main(String[] args){ String str = "edfreqwsazxet"; char ch = '$'; int n = str.length(); int k = 4; countOperations(n, k);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program to implement# the above approach# Function to find the minimum# number of operations requireddef countOperations(n, k): # Maximum number of characters that # can be changed in one operation div = 2 * k + 1 # If length of the less than # maximum number of characters that # can be changed in an operation if (n // 2 <= k): print(1) # Set the last index as the # index for the operation if (n > k): print(k + 1) else: print(n) # Otherwise else: # If size of the is # equal to the maximum number # of characters in an operation if (n % div == 0): # Find the number of # operations required oprn = n // div print(oprn) # Find the starting position pos = k + 1 print(pos, end = " ") for i in range(1, oprn + 1): # Print i-th index print(pos, end = " ") # Shift to next index pos += div # Otherwise else: # Find the number of # operations required oprn = n // div + 1 print(oprn) pos = n % div # If n % div exceeds k if (n % div > k): pos -= k for i in range(1, oprn + 1): # Print i-th index print(pos, end = " ") # Shift to next index pos += div# Driver Codeif __name__ == '__main__': str = "edfreqwsazxet" ch = '$' n = len(str) k = 4 countOperations(n, k)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the minimum// number of operations requiredstatic void countOperations(int n, int k){ // Maximum number of characters that // can be changed in one operation int div = 2 * k + 1; // If length of the String less than // maximum number of characters that // can be changed in an operation if (n / 2 <= k) { Console.Write(1 + "\n"); // Set the last index as the // index for the operation if (n > k) Console.Write(k + 1); else Console.Write(n); } // Otherwise else { // If size of the String is // equal to the maximum number // of characters in an operation if (n % div == 0) { // Find the number of // operations required int oprn = n / div; Console.Write(oprn + "\n"); // Find the starting position int pos = k + 1; Console.Write(pos + " "); for(int i = 1; i <= oprn; i++) { // Print i-th index Console.Write(pos + " "); // Shift to next index pos += div; } } // Otherwise else { // Find the number of // operations required int oprn = n / div + 1; Console.Write(oprn + "\n"); int pos = n % div; // If n % div exceeds k if (n % div > k) pos -= k; for(int i = 1; i <= oprn; i++) { // Print i-th index Console.Write(pos + " "); // Shift to next index pos += div; } } }}// Driver Codepublic static void Main(String[] args){ String str = "edfreqwsazxet"; int n = str.Length; int k = 4; countOperations(n, k);}} // This code is contributed by Rohit_ranjan |
Javascript
<script>// javascript program to implement// the above approach // Function to find the minimum // number of operations required function countOperations(n , k) { // Maximum number of characters that // can be changed in one operation var div = 2 * k + 1; // If length of the String less than // maximum number of characters that // can be changed in an operation if (n / 2 <= k) { document.write(1 + "<br/>"); // Set the last index as the // index for the operation if (n > k) document.write(k + 1); else document.write(n); } // Otherwise else { // If size of the String is // equal to the maximum number // of characters in an operation if (n % div == 0) { // Find the number of // operations required var oprn = parseInt(n / div); document.write(oprn + "<br/>"); // Find the starting position var pos = k + 1; document.write(pos + " "); for (i = 1; i <= oprn; i++) { // Print i-th index document.write(pos + " "); // Shift to next index pos += div; } } // Otherwise else { // Find the number of // operations required var oprn = parseInt(n / div + 1); document.write(oprn + "<br/>"); var pos = n % div; // If n % div exceeds k if (n % div > k) pos -= k; for (i = 1; i <= oprn; i++) { // Print i-th index document.write(pos + " "); // Shift to next index pos += div; } } } } // Driver Code var str = "edfreqwsazxet"; var ch = '$'; var n = str.length; var k = 4; countOperations(n, k);// This code contributed by Rajput-Ji</script> |
Output:
2 4 13
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
