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

给定一个数字字符串 S ，任务是找到具有其左旋等于其右旋的最长子序列的最大长度。

例：

输入： S = “100210601”

输出： 4

解释：

子序列“0000”满足必要条件。

子序列“1010”在左旋和右旋时分别生成字符串“0101”和“0101”。旋转相同。因此，“1010”也满足条件。

因此，这种子序列的最大长度为4。

输入： S = “252525”

输出： 6

解释：

子序列“252525”在左旋和右旋时分别生成字符串“525252”和“525252”。旋转相同。因此，“252525”满足要求的条件。

Naive Approach: 解决问题的最简单方法是生成给定字符串的所有可能子序列，并对于每个子序列检查其左和右旋转是否相等。

时间复杂度： O(2 N * N)

辅助空间： O(N)

Efficient Approach: 优化上述方法的主要观察结果是，子序列应该由一个 单个字符 或由 交替出现的两个字符 形成的偶数长度。

说明：

str = “2424”

字符串的左旋 = “4242”

字符串的右旋 = “4242”

正如我们所看到的，由于数字长度为偶数，有两个字符交替出现，因此给定数字的左旋和右旋是相等的。

str = “24242”

字符串的左旋 = “42422”

字符串的右旋 = “22424”

正如我们所看到的，由于数字长度为奇数，有两个字符交替出现，因此给定数字的左旋和右旋不相等。

执行以下步骤来解决问题：

生成所有可能的两位数字。
对于生成的每个两位数字，检查字符串中两个数字是否交替出现。保持递增的计数器以存储该特定组合的交替子序列的长度。
在字符串的整个遍历之后，检查两个数字是否相等。如果为真，则将 计数器 更新为所需答案。如果两个数字相等，则更新 计数器 或如果计数器为奇数或偶数，则更新为 count-1 答案。
对于所有可能的组合重复以上步骤，并打印得到的最大 计数器 。

下面是上述方法的实现：

// C++ 程序实现
// 上述方法
#include <bits/stdc++.h>
using namespace std;
 
// 查找具有相等左右旋转的最长子序列的函数
int findAltSubSeq(string s)
{
    // 字符串的长度
    int n = s.size(), ans = INT_MIN;
 
    // 遍历所有可能的组合
    // 一个两位数字
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            int cur = 0, f = 0;
 
            // 检查当前组合出现的交替情况
            for (int k = 0; k < n; k++) {
 
                if (f == 0 and s[k] - '0' == i) {
                    f = 1;
 
                    // 增加当前值
                    cur++;
                }
                else if (f == 1 and s[k] - '0' == j) {
                    f = 0;
 
                    // 增加当前值
                    cur++;
                }
            }
 
            // 如果获得了奇数长度的交替序列
            if (i != j and cur % 2 == 1)
 
                // 缩小到偶数长度
                cur--;
 
            // 更新答案以存储最大值
            ans = max(cur, ans);
        }
    }
 
    // 返回答案
    return ans;
}
 
// 主函数
int main()
{
    string s = "100210601";
    cout << findAltSubSeq(s);
 
    return 0;
}

输出:

时间复杂度： O(N)，因为我们使用一个循环遍历N次，所以它将花费O(N)的时间
辅助空间： O(1)，因为我们不使用任何额外空间。