Minimum replacements required to obtain a K-periodic palindromic string
Given a string S of length N and an integer K, the task is to find the minimum character replacements required to make the string palindromic as well as K-periodic.
Examples:
Input: S = “abaaba”, K = 2
Output: 2
Explanation: The optimal way is to transform the string to “aaaaaa”. Therefore, the minimum number of changes required is 2.Input: S = “aabbcbbcb”, K = 3
Output: 2
Explanation:
The optimal way is to transform the string to ”bcbbcbbcb”. Therefore, the minimum number of changes required is 2.
Approach: To minimize the number of changes required to make in the string, observe the following property of the transformed string which is palindromic and K-periodic:
- A K-periodic string can be made only by concatenating several palindromic strings having length K.
- All the characters at positions i, K – i – 1, i + K, 2K – i – 1, i + 2K, 3K – i – 1, i + 3K, … for all 0 ? i < K, are equal.
The problem reduces to making all the characters equal to the one which appears the maximum number of times at these positions in the given string. Follow the steps below to solve the above problem:
- Initialize a variable ans with 0 that stores the minimum changes required to satisfy the given condition.
- Iterate over the range [0, K / 2] using the variable i.
- Create a hashmap, mp to store the frequency of each character.
- Iterate over the characters in the string starting from i in intervals of K using a variable j and store the frequency of each character.
- Iterate the string in reverse, starting from (N – i – 1) in intervals of K using a variable j and store the frequency of each character. If K is odd and i = K / 2, then break out of the loop.
- Find the maximum frequency of a character among the visited one and store it in a variable, say curr_max.
- After the above steps, if K is odd and i = K/2, then increment ans by (N/K – curr_max)Otherwise, increment ans by (N/K – 2*curr_max).
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of changes to make the string K- // periodic and palindrome int findMinimumChanges( int N, int K, string S) { // Initialize ans with 0 int ans = 0; // Iterate from 0 to (K+1) / 2 for ( int i = 0; i < (K + 1) / 2; i++) { // Store frequency of character map< char , int > mp; // Iterate through all indices, // i, i+K, i+2k.... and store // the frequency of character for ( int j = i; j < N; j += K) { // Increase the frequency // of current character mp[S[j]]++; } // Iterate through all indices // K-i, 2K-i, 3K-i.... and store // the frequency of character for ( int j = N - i - 1; j >= 0; j -= K) { // If K is odd & i is samw // as K/2, break the loop if (K & 1 and i == K / 2) break ; // Increase the frequency // of current character mp[S[j]]++; } // Find the maximum frequency // of a character among all // visited characters int curr_max = INT_MIN; for ( auto p : mp) curr_max = max(curr_max, p.second); // If K is odd and i is same // as K/2 then, only N/K // characters is visited if (K & 1 and i == K / 2) ans += (N / K - curr_max); // Otherwise N/K * 2 characters // has visited else ans += (N / K * 2 - curr_max); } // Return the result return ans; } // Driver Code int main() { string S = "aabbcbbcb" ; int N = S.length(); int K = 3; // Function Call cout << findMinimumChanges(N, K, S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum number // of changes to make the String K- // periodic and palindrome static int findMinimumChanges( int N, int K, char [] S) { // Initialize ans with 0 int ans = 0 ; // Iterate from 0 to (K+1) / 2 for ( int i = 0 ; i < (K + 1 ) / 2 ; i++) { // Store frequency of character HashMap<Character, Integer> mp = new HashMap<>(); // Iterate through all indices, // i, i+K, i+2k.... and store // the frequency of character for ( int j = i; j < N; j += K) { // Increase the frequency // of current character if (mp.containsKey(S[j])) { mp.put(S[j], mp.get(S[j]) + 1 ); } else { mp.put(S[j], 1 ); } } // Iterate through all indices // K-i, 2K-i, 3K-i.... and store // the frequency of character for ( int j = N - i - 1 ; j >= 0 ; j -= K) { // If K is odd & i is samw // as K/2, break the loop if (K % 2 == 1 && i == K / 2 ) break ; // Increase the frequency // of current character if (mp.containsKey(S[j])) { mp.put(S[j], mp.get(S[j]) + 1 ); } else { mp.put(S[j], 1 ); } } // Find the maximum frequency // of a character among all // visited characters int curr_max = Integer.MIN_VALUE; for (Map.Entry<Character, Integer> p : mp.entrySet()) { curr_max = Math.max(curr_max, p.getValue()); } // If K is odd and i is same // as K/2 then, only N/K // characters is visited if ((K % 2 == 1 ) && i == K / 2 ) ans += (N / K - curr_max); // Otherwise N/K * 2 characters // has visited else ans += (N / K * 2 - curr_max); } // Return the result return ans; } // Driver Code public static void main(String[] args) { String S = "aabbcbbcb" ; int N = S.length(); int K = 3 ; // Function Call System.out.print(findMinimumChanges( N, K, S.toCharArray())); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the # above approach import sys # Function to find the minimum # number of changes to make # the string K- periodic and # palindrome def findMinimumChanges(N, K, S): # Initialize ans with 0 ans = 0 # Iterate from 0 to (K+1) / 2 for i in range ((K + 1 ) / / 2 ): # Store frequency of # character mp = {} # Iterate through all indices, # i, i+K, i+2k.... and store # the frequency of character for j in range (i, N, K): # Increase the frequency # of current character mp[S[j]] = mp.get(S[j], 0 ) + 1 # Iterate through all indices # K-i, 2K-i, 3K-i.... and store # the frequency of character j = N - i - 1 while (j > = 0 ): # If K is odd & i is samw # as K/2, break the loop if ((K & 1 ) and (i = = K / / 2 )): break # Increase the frequency # of current character mp[S[j]] = mp.get(S[j], 0 ) + 1 j - = K # Find the maximum frequency # of a character among all # visited characters curr_max = - sys.maxsize - 1 for key, value in mp.items(): curr_max = max (curr_max, value) # If K is odd and i is same # as K/2 then, only N/K # characters is visited if ((K & 1 ) and (i = = K / / 2 )): ans + = (N / / K - curr_max) # Otherwise N/K * 2 # characters has visited else : ans + = (N / / K * 2 - curr_max) # Return the result return ans # Driver Code if __name__ = = '__main__' : S = "aabbcbbcb" N = len (S) K = 3 # Function Call print (findMinimumChanges(N, K, S)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum number // of changes to make the String K- // periodic and palindrome static int findMinimumChanges( int N, int K, char [] S) { // Initialize ans with 0 int ans = 0; // Iterate from 0 to (K+1) / 2 for ( int i = 0; i < (K + 1) / 2; i++) { // Store frequency of character Dictionary< char , int > mp = new Dictionary< char , int >(); // Iterate through all indices, // i, i+K, i+2k.... and store // the frequency of character for ( int j = i; j < N; j += K) { // Increase the frequency // of current character if (mp.ContainsKey(S[j])) { mp[S[j]]++; } else { mp.Add(S[j], 1); } } // Iterate through all indices // K-i, 2K-i, 3K-i.... and store // the frequency of character for ( int j = N - i - 1; j >= 0; j -= K) { // If K is odd & i is samw // as K/2, break the loop if (K % 2 == 1 && i == K / 2) break ; // Increase the frequency // of current character if (mp.ContainsKey(S[j])) { mp[S[j]]++; } else { mp.Add(S[j], 1); } } // Find the maximum frequency // of a character among all // visited characters int curr_max = int .MinValue; foreach (KeyValuePair< char , int > p in mp) { curr_max = Math.Max(curr_max, p.Value); } // If K is odd and i is same // as K/2 then, only N/K // characters is visited if ((K % 2 == 1) && i == K / 2) ans += (N / K - curr_max); // Otherwise N/K * 2 characters // has visited else ans += (N / K * 2 - curr_max); } // Return the result return ans; } // Driver Code public static void Main(String[] args) { String S = "aabbcbbcb" ; int N = S.Length; int K = 3; // Function Call Console.Write(findMinimumChanges( N, K, S.ToCharArray())); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum number // of changes to make the string K- // periodic and palindrome function findMinimumChanges(N, K, S) { // Initialize ans with 0 var ans = 0; // Iterate from 0 to (K+1) / 2 for ( var i = 0; i < parseInt((K + 1) / 2); i++) { // Store frequency of character var mp = new Map(); // Iterate through all indices, // i, i+K, i+2k.... and store // the frequency of character for ( var j = i; j < N; j += K) { // Increase the frequency // of current character if (mp.has(S[j])) { mp.set(S[j], mp.get(S[j])+1); } else { mp.set(S[j], 1); } } // Iterate through all indices // K-i, 2K-i, 3K-i.... and store // the frequency of character for ( var j = N - i - 1; j >= 0; j -= K) { // If K is odd & i is samw // as K/2, break the loop if ((K & 1) && i == parseInt(K / 2)) break ; // Increase the frequency // of current character if (mp.has(S[j])) { mp.set(S[j], mp.get(S[j])+1); } else { mp.set(S[j], 1); } } // Find the maximum frequency // of a character among all // visited characters var curr_max = -1000000000; mp.forEach((value, key) => { curr_max = Math.max(curr_max, value); }); // If K is odd and i is same // as K/2 then, only N/K // characters is visited if (K & 1 && i == parseInt(K / 2)) ans += (parseInt(N / K) - curr_max); // Otherwise N/K * 2 characters // has visited else ans += (parseInt(N / K) * 2 - curr_max); } // Return the result return ans; } // Driver Code var S = "aabbcbbcb" ; var N = S.length; var K = 3; // Function Call document.write( findMinimumChanges(N, K, S)); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us