Find two equal subsequences of maximum length with at least one different index
Given a string str, the task is to find the maximum length K such that there exist two sub-sequences A and B each of length K such that A = B and number of common indices between A and B is at most K – 1.
Examples:
Input: str = “w3wiki”
Output: 12
The two subsequences are
str[0…1] + str[3…12] = “geksforBeginner”
and str[0] + str[2…12] = “geksforBeginner”.
Input: str = “abcddefg”
Output: 7
Approach: Find any pair of the same letter with a minimum number of letters between them let say this minimum number be X, now the answer of the problem is len(str) – (X + 1). One is added in X to not take count of one letter from the pair.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const int MAX = 26; // Function to return the required // length of the subsequences int maxLength(string str, int len) { // To store the result int res = 0; // To store the last visited // position of lowercase letters int lastPos[MAX]; // Initialisation of frequency array to -1 to // indicate no character has previously occurred for ( int i = 0; i < MAX; i++) { lastPos[i] = -1; } // For every character of the string for ( int i = 0; i < len; i++) { // Get the index of the current character int C = str[i] - 'a' ; // If the current character has // appeared before in the string if (lastPos[C] != -1) { // Update the result res = max(len - (i - lastPos[C] - 1) - 1, res); } // Update the last position // of the current character lastPos[C] = i; } return res; } // Driver code int main() { string str = "w3wiki" ; int len = str.length(); cout << maxLength(str, len); return 0; } |
Java
// Java implementation of the approach class GFG { static int MAX = 26 ; // Function to return the required // length of the subsequences static int maxLength(String str, int len) { // To store the result int res = 0 ; // To store the last visited // position of lowercase letters int lastPos[] = new int [MAX]; // Initialisation of frequency array to -1 to // indicate no character has previously occurred for ( int i = 0 ; i < MAX; i++) { lastPos[i] = - 1 ; } // For every character of the String for ( int i = 0 ; i < len; i++) { // Get the index of the current character int C = str.charAt(i) - 'a' ; // If the current character has // appeared before in the String if (lastPos[C] != - 1 ) { // Update the result res = Math.max(len - (i - lastPos[C] - 1 ) - 1 , res); } // Update the last position // of the current character lastPos[C] = i; } return res; } // Driver code public static void main(String args[]) { String str = "w3wiki" ; int len = str.length(); System.out.println(maxLength(str, len)); } } // This code is contributed by Arnab Kundu |
Python3
# Python implementation of the approach MAX = 26 ; # Function to return the required # length of the subsequences def maxLength( str , len ): # To store the result res = 0 ; # To store the last visited # position of lowercase letters lastPos = [ 0 ] * MAX ; # Initialisation of frequency array to -1 to # indicate no character has previously occurred for i in range ( MAX ): lastPos[i] = - 1 ; # For every character of the String for i in range ( len ): # Get the index of the current character C = ord ( str [i]) - ord ( 'a' ); # If the current character has # appeared before in the String if (lastPos[C] ! = - 1 ): # Update the result res = max ( len - (i - lastPos[C] - 1 ) - 1 , res); # Update the last position # of the current character lastPos[C] = i; return res; # Driver code if __name__ = = '__main__' : str = "w3wiki" ; len = len ( str ); print (maxLength( str , len )); # This code is contributed by 29AjayKumar |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 26; // Function to return the required // length of the subsequences static int maxLength( string str, int len) { // To store the result int res = 0; // To store the last visited // position of lowercase letters int []lastPos = new int [MAX]; // Initialisation of frequency array to -1 to // indicate no character has previously occurred for ( int i = 0; i < MAX; i++) { lastPos[i] = -1; } // For every character of the String for ( int i = 0; i < len; i++) { // Get the index of the current character int C = str[i] - 'a' ; // If the current character has // appeared before in the String if (lastPos[C] != -1) { // Update the result res = Math.Max(len - (i - lastPos[C] - 1) - 1, res); } // Update the last position // of the current character lastPos[C] = i; } return res; } // Driver code public static void Main() { string str = "w3wiki" ; int len = str.Length; Console.WriteLine(maxLength(str, len)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach var MAX = 26; // Function to return the required // length of the subsequences function maxLength(str, len) { // To store the result var res = 0; // To store the last visited // position of lowercase letters var lastPos = Array(MAX); // Initialisation of frequency array to -1 to // indicate no character has previously occurred for ( var i = 0; i < MAX; i++) { lastPos[i] = -1; } // For every character of the string for ( var i = 0; i < len; i++) { // Get the index of the current character var C = str[i].charCodeAt(0) - 'a' .charCodeAt(0); // If the current character has // appeared before in the string if (lastPos[C] != -1) { // Update the result res = Math.max(len - (i - lastPos[C] - 1) - 1, res); } // Update the last position // of the current character lastPos[C] = i; } return res; } // Driver code var str = "w3wiki" ; var len = str.length; document.write( maxLength(str, len)); </script> |
12
Time Complexity: O(n) where n is the length of the input string.
Auxiliary Space: O(26) ⇒ O(1), no extra space is required, so it is a constant.
Contact Us