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)，因為我們不使用任何動態空間。

在本教程中，我們學習瞭如何找到具有相同左右旋轉的子序列的最大長度。程式設計師可以嘗試使用程式碼查詢給定字串的所有可能的子序列，從而使用暴力方法來解決。