C++ 找到左右旋转相同数字的最长子序列

在这个问题中，我们需要找到具有相同左旋和右旋的最长子序列的最大长度。左旋表示将字符串中的所有字符向左移动，并将第一个字符移到末尾。右旋表示将字符串中的所有字符向右移动，并将最后一个字符移到开头。

问题陈述 - 我们给出了一个包含数字的字符串str，并需要找到具有相同左旋和右旋的最长子序列。

示例

输入 - str = “323232”，

输出 - 6

解释 - 具有相同左旋和右旋的最长子序列是“323232”。左旋是“232323”，右旋是“232323”。

输入 - str = ‘00010100’

输出 - 6

解释 - 具有相同左旋和右旋的最长子序列是“000000”。

输入 - str = ‘092312110431010’

输出 - 6

解释 - 具有相同左旋和右旋的长度为6的子序列有2个可能的子序列。第一个是“010101”，第二个是“101010”。

方法1

在这种方法中，我们将找到给定字符串的所有可能子序列。然后，我们将检查字符串的左旋和右旋是否相同。我们将使用递归方法来找到所有可能的子序列。

步骤

• 使用零初始化’ maxLen ‘全局变量以存储具有相同左旋和右旋的最长子序列的长度。

• 定义isRightSameLeft()函数以检查字符串是否具有相同的左旋和右旋。

  • 在函数内部，使用substr()方法将字符串向左和向右旋转。
• getAllSubSeq()函数用于找到给定字符串的所有可能子序列。

• 定义基本案例。如果’str’为空，我们获取子序列并执行isRightSameLeft()函数以检查子序列是否具有相同的左旋和右旋。如果是，则如果其长度大于’ maxLen ‘变量的当前值，则更新’ maxLen ‘变量的值。

• 在从’str’中删除第一个字符并将其与’out’字符串连接后，进行递归调用。

• 移除第一个字符并保持’out’字符串不变后，再次进行递归函数调用。在此递归调用中，我们排除’str’的第一个字符。

示例

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

// Defining global variable to store the length of the longest subsequence according to the given condition
int maxLen = 0;
//  function to check if the string is the same after the left rotation
bool isRightSameLeft(string str) {
   int len = str.length();
   return str.substr(1, len - 1) + str[0] == str[len - 1] + str.substr(0, len - 1);
}
// function to get all subsequences of a string
void getAllSubSeqs(string str, string out) {
   // If the string is empty, we get the subsequences. Check if its left and right rotation is the same
   if (str.empty()) {
      if (isRightSameLeft(out))
          maxLen = max(maxLen, (int)out.length());
      return;
   }
   // Recursive case remove the first character from str, and add it to the output
   getAllSubSeqs(str.substr(1), out + str[0]);
   // remove the first character from str, and drop it
   if (str.length() > 1)
      getAllSubSeqs(str.substr(1), out);
}
int main() {
   string str = "323232";
   string out = "";
   getAllSubSeqs(str, out);
   cout << "The longest subsequence of str having same left and right rotation is " << maxLen;
   return 0;
}

输出

The longest subsequence of str having same left and right rotation is 6

时间复杂度 – O(N*2N)。这里 O(N) 是用于比较左旋和右旋，O(2N) 用于找到所有可能的子序列。

空间复杂度 – O(1)，因为我们不使用额外的空间。

方法2

在这里，我们对上述方法进行了优化。我们可以观察样本输入的解决方案。子序列的左旋和右旋只有当子序列包含相同的字符或两个不同的字符交替出现，并且长度为偶数时才相同。

步骤

• 使用两个嵌套循环来组合任意两个数字。

• 定义‘cnt’变量来找到包含两个数字交替出现的子序列的长度，并初始化为零。

• 定义布尔类型的‘first’变量来跟踪下一个字符是第i个还是第j个。

• 使用循环来遍历字符串。

• 如果first true 并且 str[k] – ‘0’ I，交替改变‘first’的值，并将‘cnt’增加1。

• 如果first false 并且 str[k] – ‘0’ j，再次交替改变‘first’的值，并将‘cnt’增加1。

• 如果i和j不相等，并且‘cnt’的值为奇数，则将其减1。

• 如果‘cnt’的值大于‘res’，则更新‘res’变量的值。

示例

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

int getLongSubSeq(string str) {
   // Store the length of the string
   int len = str.size(), res = 0;
   // Traverse the all possible combination of two digits
   for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
          // to store the length of an alternating sequence of the current combination
          int cnt = 0;
          // to track the turn of the ith or jth digit
          bool first = true;
          // traverse the string
          for (int k = 0; k < len; k++) {
              // If the current digit is equal to I, and the first is true, increment the count
              if (first == true and str[k] - '0' == i) {
                  first = false;
                  cnt++;
              } else if (first == false and str[k] - '0' == j) {
                  // If the current digit is equal to j, and the first is false, increment the count
                  first = true;
                  cnt++;
              }
          }
          // If the sequence is odd and i and j are different, decrement the count
          if (i != j and cnt % 2 == 1)
              cnt--;
          // Update the answer
          res = max(cnt, res);
       }
   }
   return res;
}
int main() {
   string str = "00010100";
   cout << "The longest subsequence of str having same left and right rotation is " << getLongSubSeq(str);
   return 0;
}

输出

The longest subsequence of str having same left and right rotation is 6

时间复杂度 – O(1010N)，因为我们从包含数字组合的字符串中找到子序列。

空间复杂度 – O(1)，因为我们不使用动态空间。

这个教程教会了我们两种方法来找到包含相同左右旋转的最长子序列。第一种方法是朴素方法，非常耗时，我们无法用它处理大量输入。

第二种方法进行了优化，因为其时间复杂度几乎等于O(N)。