Java 查找具有相同左旋和右旋的数字的最长子序列

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

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

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

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

示例

输入 - str = “9898798”

输出 - 6

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

输入 - str = ‘12345678’

输出 - 2

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

输入 - ‘327787767777’

输出 - 8

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

方法

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

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

步骤

• 将’len’变量初始化为字符串的长度，并将’cnt’初始化为0，以存储子序列的最大长度。

• 使用两个嵌套循环从0到9进行遍历，得到每个数字的组合。

• 定义’cur_len’变量来存储当前子序列的长度。同时，定义’firstDigit’变量来跟踪下一个数字是否是pth或者qth个数字。

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

• 如果firstDigit 0 && str.charAt(k) – ‘0’ pI为真，则将firstDigit的值改为1，并将cur加1。

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

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

• 更新’cnt’的值，如果’cur_len’的值大于’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)，因为我们不使用任何动态空间。

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