Java程序：求解具有相同左右旋转的最长子序列

---

在这个问题中，我们需要找到具有相同左右旋转的最长子序列的长度。

我们可以使用暴力方法解决这个问题，找到给定字符串的所有可能的子序列，并逐一检查每个子序列是否具有相同的左右旋转。我们找到此类子序列的最大长度。这种方法的问题在于它非常耗时，因为它的时间复杂度为O(2N)。

因此，我们将学习在这种方法中编写优化的代码。

问题陈述– 我们给定一个包含N个数字字符的字符串str。我们需要找到给定字符串具有相同左右旋转的最长子序列。

示例

输入– str = "9898798"

输出– 6

解释– 我们具有相同左右旋转的最长子序列是989898。

输入– str = ‘12345678’

输出– 2

解释– 我们可以选择任何长度为2的子序列，因为它总是具有相同的左右旋转。

输入– ‘327787767777’

输出– 8

解释– 具有相同左右旋转的最长子序列是’77777777’。

方法1

在这种方法中，我们将基于一个特别的观察结果来解决这个问题。只有当字符串的所有数字都相等，或者它包含交替的两个数字且字符串长度为偶数时，字符串才可能具有相同的左右旋转。

在这里，我们将尝试找到相同或交替数字的子序列。

算法

• 用字符串长度初始化变量‘len’，用0初始化‘cnt’来存储子序列的最大长度。

• 使用两个嵌套循环从0遍历到9，并获取每个数字的组合。

• 定义变量‘cur_len’来存储当前子序列的长度。此外，定义变量‘firstDigit’来跟踪下一个数字是交替数字序列中的第p个还是第q个数字。

• 使用第三个嵌套循环遍历数字字符串。

• 如果firstDigit == 0 && str.charAt(k) - '0' == p为真，则将firstDigit的值更改为1，并将cur_len加1。

• 如果firstDigit == 1 && str.charAt(k) - '0' == q为真，则将firstDigit的值更改为0，并将‘cur_len’加1。

• 如果p和q不相等，并且‘cur_len’的值为奇数，则将‘cur_len’减1。

• 如果‘cur_len’的值大于‘cnt’的值，则更新‘cnt’的值。

• 返回‘cnt’的值。

示例

import java.util.*;
public class Main {
   static int findLongestSub(String str) {
      int len = str.length(), cnt = 0;
      // Traverse each combination of the string.
      for (int p = 0; p < 10; p++) {
          for (int q = 0; q < 10; q++) {
              int cur_len = 0, firstDigit = 0;
              // Find the alternating sequence
              for (int r = 0; r < len; r++) {
                  if (firstDigit == 0 && str.charAt(r) - '0' == p) {
                      firstDigit = 1;
                      // add 1 
                      cur_len++;
                  } else if (firstDigit == 1 && str.charAt(r) - '0' == q) {
                      firstDigit = 0;
                      // add 1 
                      cur_len++;
                  }
              }
              // If the current value is odd, decrease it by 1
              if (p != q && cur_len % 2 == 1)
                  cur_len--;
              // Update the cnt value
              cnt = Math.max(cur_len, cnt);
          }
      }
      // Return the result
      return cnt;
   }
   public static void main(String[] args) {
      String str = "9898798";
      System.out.print("The length of the longest subsequence having the same left and right rotations is "
               + findLongestSub(str));
   }
}

输出

The length of the longest subsequence having the same left and right rotations is 6

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

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

在本教程中，我们学习了如何找到具有相同左右旋转的子序列的最大长度。程序员可以尝试使用代码查找给定字符串的所有可能的子序列，从而使用暴力方法来解决。