C++ 通过替换给定字符串中的’?’得到的按字典顺序最小的具有周期K的字符串

一个字符串是周期为K的，当且仅当它每K个字符重复一次。例如，字符串 “abcabcabc” 是一个周期为3的字符串，因为它每3个字符重复一次。字符串 “abcabc?abc” 不是一个周期为3的字符串，因为字符 ‘?’ 没有每3个字符重复一次。

问题陈述

给定一个包含N个小写字符的字符串”str”和一个正整数K，目标是用小写字母替换字符串”str”中的每个字符’?’，使得结果字符串形成长度为K的周期。如果无法找到满足给定条件的字符串，则输出“-1”。

字符串”str”可以包含任意数量的小写字符，包括’a’，’b’，’c’，……，’z’。

字符串”str”也可以包含字符’?’。

正整数K必须大于或等于1。

如果无法找到满足给定条件的字符串，则程序应打印“-1”。

示例

输入

“aabb????”, K = 4

输出

aabbaabb

输入

“xxyy????”, K = 2

输出

-1

解决方案

一个直观的寻找修改后字符串的方法可以通过以下步骤实现。

生成给定字符串中“?”字符的所有可能替换组合。

• 对于每个组合，相应地替换“?”字符。

• 检查生成的字符串是否具有长度为K的周期。如果是，则将其存储为候选解。

• 在检查完所有组合之后，比较候选解并选择字典排序最小的一个。

• 返回具有长度为K的字典排序最小字符串，如果没有找到有效解，则返回“-1”。

朴素的方法涉及生成所有可能的组合，这可能计算成本很高。随着字符串的长度和“?”字符的数量增加，组合的数量将呈指数级增长。因此，这种方法对于大型输入字符串不高效。

更优化的方法是使用一个高效的算法，避免了穷举生成组合，并根据特定条件直接修改字符串，以获得具有长度为K的字典排序最小字符串。

算法

• 接受一个字符串str和一个整数K作为参数。

• 验证字符串“str”的长度是否是K的倍数。如果不是，则返回“-1”，因为无法形成长度为K的周期。

• 使用变量“i”遍历范围从0到K。

• 创建一个空的map，称为“char_freq”，用于存储字符的频率计数。

• 从索引“i”开始以每次K的增量遍历字符串“str”。

• 更新“char_freq”中遇到的每个字符的频率计数。

• 如果char_freq的大小大于2，则返回“-1”。

• 如果char_freq的大小为1，检查“?”的频率是否不为零。如果是，则将str中位置为i，i+K，i+2K等的所有“?”字符替换为“a”。

• 否则，如果char_freq的大小为2，则找到与“?”不同的字符，并将其存储在ch中。

• 将str中位置为i，i+K，i+2K等的所有“?”字符替换为ch。

• 返回修改后的字符串str。

示例：C++程序

代码片段 “stringNew()” 的设计是接受一个字符串 “str” 和一个整数 “K” 作为输入。最初，该函数验证 “str” 的长度是否被 “K” 整除。如果不是，则函数返回 -1。然而，如果长度条件满足，函数会在范围 [0, K] 上迭代。对于该范围内的每个索引 “i”，函数会创建一个名为 “char_freq” 的映射，以跟踪子字符串 “str[i: i + K]” 中每个字符的频率。然后，函数会检查 “char_freq” 的大小是否超过 2。如果条件为真，则函数返回 -1。另一方面，如果条件不满足，函数会将子字符串中的所有问号替换为 “char_freq” 中保存的最常见字符。最后，函数返回修改后的 “str”。

示例

#include <iostream>
#include <string>
#include <map>
using namespace std;

string stringNew(string &str, int K){
   // Verify whether the length of the string "str" is divisible by K.
   if (str.length() % K != 0){
      return "-1";
   }
   // Perform an iteration over the interval [0, K].
   for (int i = 0; i < K; i++){
      // Create a map to hold the frequency of characters in the substring str[i: i + K].
      map<char, int> char_freq;
      // Iterate over the string with increment of K in every iteration.
      for (int j = i; j < str.length(); j += K){
         char_freq[str[j]]++;
      }
      // If there are more than two different characters in the substring.
      if (char_freq.size() > 2){
         return "-1";
      }
      // If there is only one character in the substring.
      else if (char_freq.size() == 1){
         // If the character is '?', replace all occurrences of '?' in the substring with 'a'.
         if (char_freq['?'] != 0){
            for (int j = i; j < str.length(); j += K){
               str[j] = 'a';
            }
         }
      }
      // If there are two different characters in the substring.
      else{
         // Find a character other than '?'.
         char ch;
         for (auto &x : char_freq){
            if (x.first != '?'){
               ch = x.first;
            }
         }
         // Exchange all occurrences of '?' in the substring with ch.
         for (int j = i; j < str.length(); j += K){
            str[j] = ch;
         }
      }
   }
   // Return the modified string.
   return str;
}
int main(){
   string str = "aabb????";
   int K = 4;
   cout << "original string: "<< str << " and "<< "K = 4" <<endl;
   cout <<"new string: "<< stringNew(str, K) << endl;
   return 0;
}

输出

original string: aabb???? and K = 4
new string: aabbaabb

时间和空间复杂度分析

时间复杂度：O(N)

• 代码由嵌套循环组成。外部循环在范围[0, K]内迭代，内部循环在字符串上以增量K进行迭代。

• 外部循环的复杂度为O(K)，因为它迭代K次。

• 内部循环在字符串的一部分进行迭代，具体来说是字符串的位置i、i+K、i+2K等处的字符。内部循环迭代的次数由字符串的长度N和K的值决定。

• 总体上，代码的时间复杂度为O(K * N/K) = O(N)。

• 代码分配额外的空间来存储每个位置”i”处子字符串中字符的频率。此存储使用名为”char_freq”的映射来完成。

• 映射”char_freq”用于记录子字符串中遇到的字符的频率。由于子字符串最多可以包含两个字符（包括’?’和另一个字符），因此该映射仅存储这些不同字符的频率。

• 映射”char_freq”所需的空间与子字符串中存在的不同字符数成正比，这种情况下最多为2。

• 因此，代码的空间复杂度可以视为O(1)，因为空间使用保持恒定，不受输入大小的影响。

结论

本文提供了一个问题的简单和高效方法。文章提供了解决方案的方法、使用的算法和C++程序解决方案，以及对其时间复杂度和空间复杂度的深入分析。