C++ 以前K个字母为组成的最长字符串的字典排序最小的字符串，该字符串不包含任何重复的子串

在这个问题中，我们需要使用字母表的前K个字符生成一个字典排序最小的字符串，以便它不包含任何重复的子串。我们可以生成一个字符串，使得所有长度为2的子串都是唯一的。因此，如果所有长度为2的子串都是唯一的，所有长度为3或更长的子串也都是唯一的。

问题描述 - 给定一个正整数K。我们需要使用字母表的前K个字符生成一个新的字符串，以便生成的字符串不包含任何长度为2或更长的重复子串，并且它是字典排序最小的。

示例

输入： - K = 1

输出： - ‘aa’

解释： - 我们可以使用’m’来生成 ‘aa’，使得结果字符串包含所有长度为2或更长的唯一子串。

输入： - K = 2

输出： - ‘aabba’

解释： - ‘aabba’是我们可以使用’a’和’b’生成的字典排序最小的字符串。

输入： - K = 4

输出： - ‘aabacadbbcbdccdda’

解释： - ‘aabacadbbcbdccdda’是我们可以使用字母表的前4个字符生成的最小字符串。

方法

这种方法将使用两个嵌套循环来生成一个新的字符串，其中包含长度为2的唯一子串。

步骤

• 将’str’变量初始化为空字符串。

• 在ASCII值为97的范围内迭代到97 + k，其中97是字母’a’的ASCII值。

• 将当前字符附加到’str’中。

• 在范围I到97 + k上迭代。

• 将i和j转换为字符值并附加到str上。

• 当两个嵌套循环的迭代都完成后，在str的末尾附加’a’。

• 返回str，这是使用前K个字母生成的新字符串。

示例

#include <bits/stdc++.h>
using namespace std;

// function to return the lexicographically smallest string of length K
string getTheString(int K){
   // to store the resultant string
   string str = "";
   // Iterating over the range [97, 97 + K]
   for (int i = 97; i < 97 + K; i++){
      // appending the ith character to the string
      str = str + char(i);
      // Create a substring of length 2 consisting of the ith character and the jth character
      for (int j = i + 1; j < 97 + K; j++){
          // appending i and j to str
          str += char(i);
          str += char(j);
      }
   }
   // appending the last character to the string
   str += char(97);
   // return the resultant string
   return str;
}
int main(){
   int K = 2;
   cout << "The lexicographically smallest string is " << getTheString(K);
   return 0;
}

结果

The lexicographically smallest string is aabba

时间复杂度 – O(K * K)，因为两个循环都遍历了前K个字符。

空间复杂度 – O(K * K)，因为我们将新生成的字符串存储在’str’变量中。

在上述代码中，我们使用前k个字符生成长度为2的所有唯一子字符串。我们需要创建唯一的字符对来创建长度为2的唯一子字符串，并且这个逻辑在解决方案方法中被遵循。