dsal 使字符串K变为周期性所需的最小交换数量

使字符串`K`变为周期性所需的最小交换数量

原文：https://www.geeksforgeeks.org/minimum-number-of-swaps-required-to-make-the-string-k-periodic/

给定长度为N的字符串S以及由小写字母组成的数组A。还给出一个正整数K。任务是找到使字符串S具有周期K所需的最小交换次数（在S和A之间）。

注意：

如果对于字符串中的每个位置i，S[i] = S[i + K]，则该字符串都称为具有周期K。
一次只能将S的一个字符替换为A的字符。
A中的字符可以多次使用。

示例：

输入：S = "nihsiakyt", K = 3, A = ['n', 'i', 'p', 's', 'q']

输出：6

说明：

考虑字符串S从 0 开始的位置：

位置 3、6 应替换为n。

位置 7 应该替换为i。

位置 2、5、8 可以用A中的任何字符替换，以使字符串变为K周期性。

最后为周期为 3 的字符串："nisnisnis"。

因此，所需的最小替换为 6

输入：S = "abcdeactr", K = 4, A = ['a', 'c', 'p']

输出：5

说明：

总共需要进行 5 次更改才能使字符串具有周期 4。

方法：可以借助频率计数和哈希解决此问题。

为了解决上述问题，我们使用二维数组freq[K][26]将所有0 <= j < N的字符频率存储在j % K位置。
使用布尔数组标记数组A中存在的所有字符。
对于 0 到K范围内的所有字符，将有N / K或N / K + 1字符，它们应该相同。
因此，对于所有这些字符，我们检查哪个字符在位置i处具有最大频率，并且也出现在数组A中。
将其添加到答案中，即N / K - maxfrequency。
如果i % K < N % K我们还将在答案中加 1
因为所有此类字符都会有N / K + 1个字符i。

下面是上述方法的实现：

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 code 
int 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 periodic 
import 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 code 
public 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 periodic 
def 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 code 
if __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 periodic 
using 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 code 
public 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

输出：

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/36682.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-02》

分类

最近更新

dsal 使字符串K变为周期性所需的最小交换数量

使字符串`K`变为周期性所需的最小交换数量

C++

Java

Python3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-02》

dsal 使字符串K变为周期性所需的最小交换数量

使字符串K变为周期性所需的最小交换数量

C++

Java

Python3

C

留言

联系客服

dsal 查看更多书籍

使字符串`K`变为周期性所需的最小交换数量