Given a string S of size N and a positive integer K ( where N % K = 0), the task is to find the minimum number of characters required to be replaced such that the string is K-periodic and the K-length periodic string must be a palindrome.
Examples:
Input: S = “abaaba”, K = 3
Output: 0
Explanation: The given string is already K-periodic and the periodic string “aba” is palindromic.Input: S = “abaaba”, K = 2
Output: 2
Explanation: By changing the characters at index 1 and 4 to ‘a’, the updated string “aaaaaa” is K-periodic and the periodic string “aa” is palindromic. Therefore, minimum changes required is 2.
Approach: The idea is to create a Graph from the given string indexes and perform DFS Traversals to find the required number of changes. Follow the below steps below to solve this problem:
- Initialize a variable total as 0 to store the count of changes required.
- According to the given conditions, create a graph from the string and in the final string all characters at positions i, K ? i +1, K + i, 2K ? i +1, 2K + i, 3K ? i + 1, … for all 1 ? i ? K should be equal.
- Iterate over the range [0, N] and add an undirected edge between index i and (N – i – 1).
- Iterate over the range [0, N – M] and add an undirected edge between index i and (i + K).
- To minimize the required number of operations, make all the letters equal to the one which appears at these positions the most, which can be easily found by performing DFS Traversal on the string.
- Perform the DFS Traversal on the created graph for all unvisited nodes:
- Find the maximum element with the maximum frequency among the visited characters in that traversal(say maxFrequency).
- Update the total number of changes in characters by the difference of count of all visited characters in the DFS Traversal and the maximum frequency in the above step.
- After completing the above steps, print the value of the total 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 add an edge to graphvoid addEdge(vector<int> adj[], int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Function to perform DFS traversal on the// graph recursively from a given vertex uvoid DFS(int u, vector<int> adj[], int& cnt, vector<bool>& visited, int fre[], string S){ // Visit the current vertex visited[u] = true; // Total number of nodes // in this component cnt++; // Increment the frequency of u fre[S[u] - 'a']++; for (int i = 0; i < adj[u].size(); i++) { if (!visited[adj[u][i]]) { DFS(adj[u][i], adj, cnt, visited, fre, S); } }}// Function for finding the minimum// number changes required in given stringint minimumOperations(string& S, int m){ int V = 100; vector<int> adj[V]; int total = 0, N = S.length(); // Form the edges according to the // given conditions for (int i = 0; i < N; i++) { addEdge(adj, i, N - i - 1); addEdge(adj, N - i - 1, i); } for (int i = 0; i < N - m; i++) { addEdge(adj, i, i + m); addEdge(adj, i + m, i); } // Find minimum number of operations vector<bool> visited(V, 0); for (int i = 0; i < N; i++) { // Frequency array for finding // the most frequent character if (!visited[i]) { // Frequency array for finding // the most frequent character int fre[26] = { 0 }; int cnt = 0, maxx = -1; DFS(i, adj, cnt, visited, fre, S); // Finding most frequent character for (int j = 0; j < 26; j++) maxx = max(maxx, fre[j]); // Change rest of the characters // to most frequent one total += cnt - maxx; } } // Print total number of changes cout << total;}// Driver Codeint main(){ string S = "abaaba"; int K = 2; // Function Call minimumOperations(S, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to add an edge to graphstatic void addEdge(Vector<Integer> adj[], int u, int v){ adj[u].add(v); adj[v].add(u);}static int cnt = 0;static boolean[] visited;// Function to perform DFS traversal on the// graph recursively from a given vertex ustatic void DFS(int u, Vector<Integer> adj[], int fre[], String S){ // Visit the current vertex visited[u] = true; // Total number of nodes // in this component cnt++; // Increment the frequency of u fre[S.charAt(u) - 'a']++; for(int i = 0; i < adj[u].size(); i++) { if (!visited[adj[u].get(i)]) { DFS(adj[u].get(i), adj, fre, S); } }}// Function for finding the minimum// number changes required in given Stringstatic void minimumOperations(String S, int m){ int V = 100; @SuppressWarnings("unchecked") Vector<Integer> []adj = new Vector[V]; int total = 0, N = S.length(); for(int i = 0; i < adj.length; i++) adj[i] = new Vector<Integer>(); // Form the edges according to the // given conditions for(int i = 0; i < N; i++) { addEdge(adj, i, N - i - 1); addEdge(adj, N - i - 1, i); } for(int i = 0; i < N - m; i++) { addEdge(adj, i, i + m); addEdge(adj, i + m, i); } // Find minimum number of operations visited = new boolean[V]; for(int i = 0; i < N; i++) { // Frequency array for finding // the most frequent character if (!visited[i]) { // Frequency array for finding // the most frequent character int fre[] = new int[26]; cnt = 0; int maxx = -1; DFS(i, adj, fre, S); // Finding most frequent character for(int j = 0; j < 26; j++) maxx = Math.max(maxx, fre[j]); // Change rest of the characters // to most frequent one total += cnt - maxx; } } // Print total number of changes System.out.print(total);}// Driver Codepublic static void main(String[] args){ String S = "abaaba"; int K = 2; // Function Call minimumOperations(S, K);}}// This code is contributed by aashish1995 |
Python3
# Python3 program for the above approachimport syssys.setrecursionlimit(1500)# Function to add an edge to graphdef addEdge(u, v): global adj adj[u].append(v) adj[v].append(u)# Function to perform DFS traversal on the# graph recursively from a given vertex udef DFS(u, fre, S): global visited, adj, cnt # Visit the current vertex visited[u] = 1 # Total number of nodes # in this component cnt += 1 # Increment the frequency of u fre[ord(S[u]) - ord('a')] += 1 for i in adj[u]: if (visited[i] == 0): DFS(i, fre, S)# Function for finding the minimum# number changes required in given stringdef minimumOperations(S, m): global adj, visited, cnt total, N = 0, len(S) # Form the edges according to the # given conditions for i in range(N): addEdge(i, N - i - 1) addEdge(N - i - 1, i) for i in range(N-m): addEdge(i, i + m) addEdge(i + m, i) for i in range(N): # Frequency array for finding # the most frequent character if (not visited[i]): # Frequency array for finding # the most frequent character fre = [0] * 26 cnt, maxx = 0, -1 DFS(i, fre, S) # Finding most frequent character for j in range(26): maxx = max(maxx, fre[j]) # Change rest of the characters # to most frequent one total += cnt - maxx # Print total number of changes print (total)# Driver Codeif __name__ == '__main__': adj = [[] for i in range(101)] visited, cnt = [0 for i in range(101)], 0 S = "abaaba" K = 2 # Function Call minimumOperations(S, K)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to add an edge to graphstatic void addEdge(List<int> []adj, int u, int v){ adj[u].Add(v); adj[v].Add(u);}static int cnt = 0;static bool[] visited;// Function to perform DFS traversal on the// graph recursively from a given vertex ustatic void DFS(int u, List<int> []adj, int []fre, String S){ // Visit the current vertex visited[u] = true; // Total number of nodes // in this component cnt++; // Increment the frequency of u fre[S[u] - 'a']++; for(int i = 0; i < adj[u].Count; i++) { if (!visited[adj[u][i]]) { DFS(adj[u][i], adj, fre, S); } }}// Function for finding the minimum// number changes required in given Stringstatic void minimumOperations(String S, int m){ int V = 100; List<int> []adj = new List<int>[V]; int total = 0, N = S.Length; for(int i = 0; i < adj.Length; i++) adj[i] = new List<int>(); // Form the edges according to the // given conditions for(int i = 0; i < N; i++) { addEdge(adj, i, N - i - 1); addEdge(adj, N - i - 1, i); } for(int i = 0; i < N - m; i++) { addEdge(adj, i, i + m); addEdge(adj, i + m, i); } // Find minimum number of operations visited = new bool[V]; for(int i = 0; i < N; i++) { // Frequency array for finding // the most frequent character if (!visited[i]) { // Frequency array for finding // the most frequent character int []fre = new int[26]; cnt = 0; int maxx = -1; DFS(i, adj, fre, S); // Finding most frequent character for(int j = 0; j < 26; j++) maxx = Math.Max(maxx, fre[j]); // Change rest of the characters // to most frequent one total += cnt - maxx; } } // Print total number of changes Console.Write(total);}// Driver Codepublic static void Main(String[] args){ String S = "abaaba"; int K = 2; // Function Call minimumOperations(S, K);}}// This code is contributed by aashish1995 |
Javascript
<script> // Javascript program for the above approach // Function to add an edge to graph function addEdge(adj, u, v) { adj[u].push(v); adj[v].push(u); } let cnt = 0; let visited; // Function to perform DFS traversal on the // graph recursively from a given vertex u function DFS(u, adj, fre, S) { // Visit the current vertex visited[u] = true; // Total number of nodes // in this component cnt++; // Increment the frequency of u fre[S[u].charCodeAt() - 'a'.charCodeAt()]++; for(let i = 0; i < adj[u].length; i++) { if (!visited[adj[u][i]]) { DFS(adj[u][i], adj, fre, S); } } } // Function for finding the minimum // number changes required in given String function minimumOperations(S, m) { let V = 100; let adj = []; for(let i = 0; i < V; i++) { adj.push([]); } let total = 0, N = S.length; for(let i = 0; i < adj.length; i++) adj[i] = []; // Form the edges according to the // given conditions for(let i = 0; i < N; i++) { addEdge(adj, i, N - i - 1); addEdge(adj, N - i - 1, i); } for(let i = 0; i < N - m; i++) { addEdge(adj, i, i + m); addEdge(adj, i + m, i); } // Find minimum number of operations visited = new Array(V); visited.fill(false); for(let i = 0; i < N; i++) { // Frequency array for finding // the most frequent character if (!visited[i]) { // Frequency array for finding // the most frequent character let fre = new Array(26); fre.fill(0); cnt = 0; let maxx = -1; DFS(i, adj, fre, S); // Finding most frequent character for(let j = 0; j < 26; j++) maxx = Math.max(maxx, fre[j]); // Change rest of the characters // to most frequent one total += cnt - maxx; } } // Print total number of changes document.write(total); } // Driver code let S = "abaaba"; let K = 2; // Function Call minimumOperations(S, K); // This code is contributed by decode2207.</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
