C++ program: find the longest subsequence of numbers with the same left and right rotation

In this problem, we need to find the maximum length of the subsequence with the same left and right rotation. Left rotation means moving all the characters in the string to the left, and moving the first character at the end. Right rotation means moving all string characters to the right and moving the last character to the beginning.

Problem Statement – We are given a string str containing numbers and need to find a subsequence of maximum length with the same left and right rotation.

Example

Input-str="323232",

Output– 6

Explanation - The longest subsequence with the same left and right rotation is "323232". Rotate it left to ‘232323’ and rotate it right to ‘232323’.

Input-str = ‘00010100’

Output– 6

Explanation – The longest subsequence with the same left and right rotation is "000000".

Input-str = ‘092312110431010’

Output– 6

Explanation – There are 2 possible subsequences of length 6 with the same left and right rotation. The first one is "010101" and the second one is "101010".

method 1

In this method we will find all possible subsequences of the given string. After that we will check if the left and right rotation of the string is the same. We will use a recursive method to find all possible subsequences.

algorithm

• Initialize the "maxLen" global variable to zero to store the length of the longest subsequence that is the same for left and right rotations.

• Define the isRightSameLeft() function to check whether the left and right rotations of the string are the same.

• Inside the function, use the substr() method to rotate the string left and right.

• getAllSubSeq() function is used to find all possible subsequences of a given string.

• Define base case. If str is empty, we get the subsequence and execute the isRightSameLeft() function to check if the subsequence has the same left and right rotation. If so, update the value of the "maxLen" variable if its length is greater than the current value of "maxLen".

• Make a recursive call after removing the first character from "str" ​​and appending the "out" string.

• After removing the first character and leaving the "out" string unchanged, make another recursive function call. In this recursive call, we exclude the first character of "str".

Example

#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;
}

Output

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

Time complexity - O(N*2N). Here O(N) for comparing left and right rotations and O(2N) for finding all possible subsequences.

Space Complexity - O(1) since we don't use extra space.

Method 2

Here, we have optimized the above method. We can observe the solution of the sample input. Left and right rotations of a subsequence are the same only if the subsequence contains the same character or alternately contains two different characters and is of even length.

algorithm

• Use two nested loops to combine any two numbers.

• Define the 'cnt' variable to find the length of a subsequence containing two numbers alternately, and initialize it to zero.

• Define the "first" variable of Boolean type to track whether the next character should be the i-th or j-th character.

• Use a loop to traverse the string.

• If first == true and str[k] - '0' == I, alternate the value of 'first' and increment 'cnt' by 1.

• If first == false and str[k] - '0' == j, alternate the value of 'first' again and increment 'cnt' by 1.

• If i and j are not equal and the "cnt" value is odd, decrement it by 1.

• If the cnt value is greater than "res", update the value of the "res" variable.

Example

#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;
}

Output

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

Time complexity - O(10*10*N), because we find subsequences from strings containing combinations of numbers.

Space complexity - O(1), because we don't use dynamic space.

This tutorial teaches us two methods to find the longest subsequence containing the same left and right rotation. The first method is the simple method, this method is very time consuming and we cannot use it for large amount of inputs.

The second method is optimized and its time complexity is almost equal to O(N).

The above is the detailed content of C++ program: find the longest subsequence of numbers with the same left and right rotation. For more information, please follow other related articles on the PHP Chinese website!