检查是否存在 2 * K + 1 个非空字符串，其连接构成给定的字符串

---

在这个问题中，我们给定一个字符串，我们需要将字符串分成 k + 1 个子字符串，使得 k + 1 个子字符串与其反转的连接可以给出原始字符串。

观察可以解决问题。如果字符串的前 k 个字符和后 k 个字符相同，我们可以说可以根据给定条件创建 k + 1 个字符串。

问题陈述 – 我们给定一个长度为 N 的字符串，包含小写字母字符和正整数 K。我们需要找到是否可以找到总共 k + 1 个字符串，使得字符串 A1、A2、A3、…、Ak、A(k + 1) 及其反转 AK、A(k-1)、…、A3、A2、A1 的连接是原始字符串 s。

示例

输入 – str = "tutorialsotut"; k = 4

输出 – 是

解释 – 我们可以创建总共 5 (4 + 1) 个字符串，分别是 't'、'u'、't'、'o' 和 'rials'，当我们根据给定条件连接它们时，我们可以得到原始字符串。

输入 – str = "ststs", k = 1

输出 – 是

解释 – 我们可以创建 's' 和 'tst' 共 2 个字符串。

输入– str = “spres”, k = 3

输出– 否

解释 – 我们无法创建总共 4 个字符串，使其符合问题陈述中给出的条件。

方法 1

在这种方法中，我们将使用 for 循环来比较字符串的前 k 个字符与后 k 个字符。如果字符串的前 K 个字符等于后 k 个字符，我们可以说可以创建 K + 1 个字符串，因此当我们将它们按实际顺序和反向顺序合并时，我们可以得到原始字符串。

算法

• 将字符串的长度存储在 'len' 变量中。

• 如果 2*k + 1 大于字符串长度，则返回 false，因为无法通过按实际顺序和反向顺序合并 k + 1 个字符串来获得原始字符串。

• 使用 for 循环遍历前 k 个字符和后 k 个字符。

• 在循环中，比较 str[i] 和 str[len - i - 1] 字符。如果它们不相同，则返回 false。

• 如果 for 循环完成所有迭代而没有执行 return 语句，则返回 true。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if we can make k+1 substrings to get the original string by concatenating strings according to the given conditions.
bool findStrings(string str, int k) {
   // get the length of the string
   int len = str.size();
   // If the length of the string is less than 2*k+1, return false
   if (2 * k + 1 > len) {
      return false;
   }
   // traverse the string to check whether the first k characters are equal to the reverse of the last k characters or not
   for (int i = 0; i < k; i++) {
      if (str[i] != str[len - i - 1]) {
          return false;
      }
   }
   // Return true if the first k characters are equal to the last k characters
   return true;
}
int main() {
   string str = "tutorialsotut";
   int K = 4;
   if (findStrings(str, K)) {
      cout << "Yes, we can make k+1 substrings according to the given conditions.";
   } else {
      cout << "No, we can't make k+1 substrings according to the given conditions.";
   }
   return 0;
}

输出

Yes, we can make k+1 substrings according to the given conditions.

时间复杂度 – O(K)，因为我们遍历字符串的前 K 个字符。

空间复杂度 – O(1)，因为我们使用常量空间。

方法 2

此方法使用 substr() 方法从原始字符串中获取子字符串。此外，我们将使用 reverse() 方法反转子字符串。

在这里，我们将比较前 k 个字符和后 k 个字符的反转。如果它们相等，我们可以说可以创建 k + 1 个子字符串，以便在合并后，我们可以得到实际字符串。

算法

• 如果给定字符串的长度大于 2*k + 1，则返回 false。

• 使用 substr() 方法并获取从 [0, k] 索引开始的子字符串，并将其存储到 'first' 变量中。

• 再次使用 substr() 方法，获取从 [len - k, len] 索引开始的子字符串，并将其存储到 'last' 变量中。

• 使用 reverse() 方法反转最后一个字符串。

• 返回 first == last 的布尔值。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if we can make k+1 substrings so that we can get the original string by concatenating strings according to the given conditions.
bool findStrings(string str, int k) {
   // get the length of the string
   int len = str.size();
   // If the length of the string is less than 2*k+1, return false
   if (2 * k + 1 > len) {
      return false;
   }
   // Get the first k characters
   string first = str.substr(0, k);
   // Get the last k characters
   string last = str.substr(len - k, k);
   // Reverse the string
   reverse(last.begin(), last.end());
   // Return true if both the strings are equal. Otherwise, return false
   return (first == last);
}
int main() {
   string str = "ststs";
   int K = 1;
   if (findStrings(str, K)) {
      cout << "Yes, we can make k+1 substrings according to the given conditions.";
   } else {
      cout << "No, we can't make k+1 substrings according to the given conditions.";
   }
   return 0;
}

输出

Yes, we can make k+1 substrings according to the given conditions.

时间复杂度 – O(K)，因为我们获取子字符串。

空间复杂度 – O(K)，因为我们将长度为 K 的子字符串存储在 'first' 和 'last' 变量中。

我们学习了两种不同的方法来解决问题。第一种方法比第二种方法更优化，因为它具有更低的空间复杂度和相同的时间复杂度。