Given a string S of length N, and an array A, consisting of lowercase letters. Also given a positive integer K. the task is to find the minimum number of swaps required (between S and A) to make string S K periodic.
Note:
- A string is said to be K periodic if for each position i in the string S[i] = S[i+K].
- In one move, only one character of S can be swapped with a character of A.
- The characters in A can be used more than once.
Examples:
Input: S = “nihsiakyt”, K = 3, A = [‘n’, ‘i’, ‘p’, ‘s’, ‘q’]
Output: 6
Explanation:
Considering 0 based positioning for the string S:
Positions 3, 6 should be replaced with ‘n’.
Position 7 should be replaced with ‘i’.
Positions 2, 5, 8 can be replaced with any character from A to make the string K periodic.
Final 3 periodic string: “nisnisnis”
Therefore minimum swaps required = 6Input: S = “abcdeactr”, K = 4, A = [‘a’, ‘c’, ‘p’]
Output: 5
Explanation:
In total 5 changes are needed to make the string 4 periodic.
Approach: This problem can be solved with help of frequency counting and hashing.
- To solve the problem mentioned above we use a 2-dimensional array freq[K][26] to store frequency of characters at position j % K for all
. - Use a boolean array to mark all characters present in array A.
- For all characters in range 0 to K there will be N / K or (N / K + 1) characters which should be same.
- So for all such characters we check which character has the maximum frequency at position i and is also present in array A.
- Add that to the answer, i.e.
. - We will also add 1 to the answer if
- because there will be N / K + 1 characters for all such characters i.
.Below is the implementation of above approach:
C++
// C++ code to find the minimum// number of swaps required to// make the string K periodic#include <bits/stdc++.h>using namespace std;int minFlip(string s, int n, int k, char a[], int p){ bool allowed[26] = { 0 }; for (int i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i] - 'a'] = true; } char freq[k][26]; // Initialize the freq array to 0 for (int i = 0; i < k; i++) for (int j = 0; j < 26; j++) freq[i][j] = 0; for (int i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k][s[i] - 'a'] += 1; } int ans = 0; // Total number of periods of // size K in the string int totalpositions = n / k; for (int i = 0; i < k; i++) { int maxfrequency = 0; for (int j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i][j] > maxfrequency and allowed[j] == true) maxfrequency = freq[i][j]; } // update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the string // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } cout << ans << endl;}// Driver codeint main(){ string S = "nihsiakyt"; int n = S.length(); int K = 3; char A[5] = { 'n', 'i', 'p', 's', 'q' }; int p = sizeof(A) / sizeof(A[0]); minFlip(S, n, K, A, p); return 0;} |
Java
// Java code to find the minimum// number of swaps required to// make the String K periodicimport java.util.*;class GFG{static void minFlip(String s, int n, int k, char a[], int p){ boolean allowed[] = new boolean[26]; for(int i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i] - 'a'] = true; } char [][]freq = new char[k][26]; // Initialize the freq array to 0 for(int i = 0; i < k; i++) for(int j = 0; j < 26; j++) freq[i][j] = 0; for(int i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k][s.charAt(i) - 'a'] += 1; } int ans = 0; // Total number of periods // of size K in the String int totalpositions = n / k; for(int i = 0; i < k; i++) { int maxfrequency = 0; for(int j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i][j] > maxfrequency && allowed[j] == true) maxfrequency = freq[i][j]; } // Update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the String // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } System.out.print(ans + "\n");}// Driver codepublic static void main(String[] args){ String S = "nihsiakyt"; int n = S.length(); int K = 3; char []A = { 'n', 'i', 'p', 's', 'q' }; int p = A.length; minFlip(S, n, K, A, p);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 code to find the minimum# number of swaps required to# make the string K periodicdef minFlip(s, n, k, a, p): allowed = [0] * 26 for i in range(p): # Mark all allowed # characters as true allowed[ord(a[i]) - ord('a')] = True freq = [[0 for x in range(26)] for y in range(k)] # Initialize the freq array to 0 for i in range(k): for j in range(26): freq[i][j] = 0 for i in range(n): # Increase the frequency # of each character freq[i % k][ord(s[i]) - ord('a')] += 1 ans = 0 # Total number of periods of # size K in the string totalpositions = n // k for i in range(k): maxfrequency = 0 for j in range(26): # Check if the current character # is present in allowed # and whether the current # frequency is greater than # all previous frequencies # for this position if (freq[i][j] > maxfrequency and allowed[j] == True): maxfrequency = freq[i][j] # Update the answer by # subtracting the maxfrequency # from total positions # if there exist extra character # at the end of the string # apart from the n/k characters # then add 1. ans += (totalpositions - maxfrequency) if (i % k < n % k): ans += 1 print(ans)# Driver codeif __name__ == "__main__": S = "nihsiakyt" n = len(S) K = 3 A = [ 'n', 'i', 'p', 's', 'q' ] p = len(A) minFlip(S, n, K, A, p)# This code is contributed by chitranayal |
C#
// C# code to find the minimum// number of swaps required to// make the String K periodicusing System;class GFG{static void minFlip(String s, int n, int k, char []a, int p){ bool []allowed = new bool[26]; for(int i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i] - 'a'] = true; } char [,]freq = new char[k, 26]; // Initialize the freq array to 0 for(int i = 0; i < k; i++) for(int j = 0; j < 26; j++) freq[i, j] = (char)0; for(int i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k, s[i] - 'a'] += (char)1; } int ans = 0; // Total number of periods // of size K in the String int totalpositions = n / k; for(int i = 0; i < k; i++) { int maxfrequency = 0; for(int j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i, j] > maxfrequency && allowed[j] == true) maxfrequency = freq[i, j]; } // Update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the String // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } Console.Write(ans + "\n");}// Driver codepublic static void Main(String[] args){ String S = "nihsiakyt"; int n = S.Length; int K = 3; char []A = { 'n', 'i', 'p', 's', 'q' }; int p = A.Length; minFlip(S, n, K, A, p);}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// Javascript code for// the above approach.function minFlip(s, n, k, a, p){ let allowed = Array.from({length: 26}, (_, i) => 0); for(let i = 0; i < p; i++) { // Mark all allowed // characters as true allowed[a[i].charCodeAt() - 'a'.charCodeAt()] = true; } let freq = new Array(k); for (var i = 0; i < freq.length; i++) { freq[i] = new Array(2); } // Initialize the freq array to 0 for(let i = 0; i < k; i++) for(let j = 0; j < 26; j++) freq[i][j] = 0; for(let i = 0; i < n; i++) { // Increase the frequency // of each character freq[i % k][s[i].charCodeAt() - 'a'.charCodeAt()] += 1; } let ans = 0; // Total number of periods // of size K in the String let totalpositions = Math.floor(n / k); for(let i = 0; i < k; i++) { let maxfrequency = 0; for(let j = 0; j < 26; j++) { // Check if the current character // is present in allowed // and whether the current // frequency is greater than // all previous frequencies // for this position if (freq[i][j] > maxfrequency && allowed[j] == true) maxfrequency = freq[i][j]; } // Update the answer by // subtracting the maxfrequency // from total positions // if there exist extra character // at the end of the String // apart from the n/k characters // then add 1. ans += (totalpositions - maxfrequency + ((i % k < n % k) ? 1 : 0)); } document.write(ans + "\n");}// Driver code let S = "nihsiakyt"; let n = S.length; let K = 3; let A = [ 'n', 'i', 'p', 's', 'q' ]; let p = A.length; minFlip(S, n, K, A, p); </script> |
Output:
6
Time Complexity: O(max(p, 26*k, n)), where p is the size of the given array, n is the length of the given string and k is a given integer.
Auxiliary Space: O(k * 26)
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!
