Longest subsequence of a number having same left and right rotation
Given a numeric string S, the task is to find the maximum length of a subsequence having its left rotation equal to its right rotation.
Examples:
Input: S = β100210601β
Output: 4
Explanation:
The subsequence β0000β satisfies the necessary condition.
The subsequence β1010β generates the string β0101β on left rotation and string β0101β on right rotation. Since both the rotations are same. Therefore, β1010β satisfies the condition as well.
Therefore, the maximum length of such subsequence is 4.
Input: S = β252525β
Output: 6
Explanation:
The subsequence β252525β generates the string β525252β on left rotation and string β525252β on right rotation. Since both the rotations are same. Therefore, the β252525β satisfies the required condition.
Naive Approach: The simplest approach to solve the problem is to generate all possible subsequences of the given string, and for each subsequence, check if its left rotation is equal to its right rotation.
Time Complexity: O(2N * N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the main observation is that the subsequence should either consist of a single character or should be of even length consisting of two characters alternatively.
Illustration:
str = β2424β
Left rotation of the string = β4242β
Right rotation of the string = β4242β
As we can see, since the number is of even length having two characters appearing alternately, therefore, the left and right rotation of the given number is equal.
str = β24242β
Left rotation of the string = β42422β
Right rotation of the string = β22424β
As we can see, since the number is of odd length having two characters appearing alternately, therefore, the left and right rotation of the given number is not equal.
Follow the steps below to solve the problem:
- Generate all possible two-digit numbers.
- For each two-digit number generated, check for the alternating occurrence of both the digits in the string. Keep incrementing count to store the length of alternating subsequence for the particular combination.
- After the entire traversal of the string, check if both the digits are equal or not. If found to be true, update count to the required answer. If both the digits are equal, then update count or count β 1 to the answer if the count is even or odd respectively.
- Repeat the above steps for all the possible combinations and print the maximum count obtained.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the longest subsequence // having equal left and right rotation int findAltSubSeq(string s) { // Length of the string int n = s.size(), ans = INT_MIN; // Iterate for all possible combinations // of a two-digit numbers for ( int i = 0; i < 10; i++) { for ( int j = 0; j < 10; j++) { int cur = 0, f = 0; // Check for alternate occurrence // of current combination for ( int k = 0; k < n; k++) { if (f == 0 and s[k] - '0' == i) { f = 1; // Increment the current value cur++; } else if (f == 1 and s[k] - '0' == j) { f = 0; // Increment the current value cur++; } } // If alternating sequence is // obtained of odd length if (i != j and cur % 2 == 1) // Reduce to even length cur--; // Update answer to store // the maximum ans = max(cur, ans); } } // Return the answer return ans; } // Driver Code int main() { string s = "100210601" ; cout << findAltSubSeq(s); return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG{ // Function to find the longest subsequence // having equal left and right rotation static int findAltSubSeq(String s) { // Length of the String int n = s.length(), ans = Integer.MIN_VALUE; // Iterate for all possible combinations // of a two-digit numbers for ( int i = 0 ; i < 10 ; i++) { for ( int j = 0 ; j < 10 ; j++) { int cur = 0 , f = 0 ; // Check for alternate occurrence // of current combination for ( int k = 0 ; k < n; k++) { if (f == 0 && s.charAt(k) - '0' == i) { f = 1 ; // Increment the current value cur++; } else if (f == 1 && s.charAt(k) - '0' == j) { f = 0 ; // Increment the current value cur++; } } // If alternating sequence is // obtained of odd length if (i != j && cur % 2 == 1 ) // Reduce to even length cur--; // Update answer to store // the maximum ans = Math.max(cur, ans); } } // Return the answer return ans; } // Driver Code public static void main(String[] args) { String s = "100210601" ; System.out.print(findAltSubSeq(s)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to implement # the above approach import sys # Function to find the longest subsequence # having equal left and right rotation def findAltSubSeq(s): # Length of the string n = len (s) ans = - sys.maxsize - 1 # Iterate for all possible combinations # of a two-digit numbers for i in range ( 10 ): for j in range ( 10 ): cur, f = 0 , 0 # Check for alternate occurrence # of current combination for k in range (n): if (f = = 0 and ord (s[k]) - ord ( '0' ) = = i): f = 1 # Increment the current value cur + = 1 elif (f = = 1 and ord (s[k]) - ord ( '0' ) = = j): f = 0 # Increment the current value cur + = 1 # If alternating sequence is # obtained of odd length if i ! = j and cur % 2 = = 1 : # Reduce to even length cur - = 1 # Update answer to store # the maximum ans = max (cur, ans) # Return the answer return ans # Driver code s = "100210601" print (findAltSubSeq(s)) # This code is contributed by Stuti Pathak |
C#
// C# Program to implement // the above approach using System; class GFG{ // Function to find the longest subsequence // having equal left and right rotation static int findAltSubSeq(String s) { // Length of the String int n = s.Length, ans = int .MinValue; // Iterate for all possible combinations // of a two-digit numbers for ( int i = 0; i < 10; i++) { for ( int j = 0; j < 10; j++) { int cur = 0, f = 0; // Check for alternate occurrence // of current combination for ( int k = 0; k < n; k++) { if (f == 0 && s[k] - '0' == i) { f = 1; // Increment the current value cur++; } else if (f == 1 && s[k] - '0' == j) { f = 0; // Increment the current value cur++; } } // If alternating sequence is // obtained of odd length if (i != j && cur % 2 == 1) // Reduce to even length cur--; // Update answer to store // the maximum ans = Math.Max(cur, ans); } } // Return the answer return ans; } // Driver Code public static void Main(String[] args) { String s = "100210601" ; Console.Write(findAltSubSeq(s)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript Program to implement // the above approach // Function to find the longest subsequence // having equal left and right rotation function findAltSubSeq(s) { // Length of the string var n = s.length, ans = -1000000000; // Iterate for all possible combinations // of a two-digit numbers for ( var i = 0; i < 10; i++) { for ( var j = 0; j < 10; j++) { var cur = 0, f = 0; // Check for alternate occurrence // of current combination for ( var k = 0; k < n; k++) { if (f == 0 && s[k] - '0' == i) { f = 1; // Increment the current value cur++; } else if (f == 1 && s[k] - '0' == j) { f = 0; // Increment the current value cur++; } } // If alternating sequence is // obtained of odd length if (i != j && cur % 2 == 1) // Reduce to even length cur--; // Update answer to store // the maximum ans = Math.max(cur, ans); } } // Return the answer return ans; } // Driver Code var s = "100210601" ; document.write( findAltSubSeq(s)); </script> |
4
Time Complexity: O(N), as we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(1), as we are not using any extra space.