Longest Subsequence with difference between characters equals to K
Given a string S consisting of lowercase letters. Find the longest subsequence of S such that the difference between the maximum and minimum occurring characters in the subsequence is exactly K.
Examples:
Input: S = ‘abcdeg’ and K = 4
Output: abcdeInput: S = ‘daaaabbbadddddeeee’, K = 1
Output: ddddddeeee
Approach: This can be solved with the following idea:
Iterate through all possible minimum and maximum character pairs (which are K characters apart). Now for each pair of characters, we check if there is a subsequence of S containing only characters between the minimum and maximum characters (inclusive) and whether both the minimum and maximum characters are present in the subsequence. If both conditions are met, and the length of the current subsequence is greater than the length of and(which is basically a variable to store the length of the longest subsequence), then the current subsequence becomes the new ans.
The steps involved in this approach are as follows:
- First, we calculate the length of the input string ‘S’ and initialize an empty string ‘ans‘ where we store the longest subsequence found.
- Then we iterate a loop from 0 to (26 – K), where 26 is the total number of alphabets. So, this loop will run for all possible min, max character pairs with a difference of ‘K’.
- Inside the loop, we define two variables ‘min_char’ and ‘max_char’ that represent the current minimum and maximum character pair being considered. We also initialize an empty string ‘curr’ that will be used to store the current subsequence being considered.
- We set two boolean flags ‘min_char_exists‘ and ‘max_char_exists‘ to false, which will be used to check if the current subsequence contains the minimum and maximum character.
- We start another loop that runs from 0 to the length of the input string ‘S’. Inside the loop, we check if the current character lies between the minimum and maximum characters or is equal to them. If it does, we add the character to the ‘curr’ string and turn the flags ‘min_char_exists’ or ‘max_char_exists’ true if the current character is equal to the minimum or maximum character, respectively.
- After the inner loop completes, we check if both ‘min_char_exists’ and ‘max_char_exists’ are true and if the length of the ‘curr’ string is greater than the length of the ‘ans’ string found so far. If both conditions are true, we update the ‘ans’ string with the current ‘curr’ string.
- At last, we return the ‘ans’ string.
Below is the code for the above approach:
C++
// C++ code for above approach #include <bits/stdc++.h> using namespace std; // Function to find the longest subsequence // with difference equals to k. string longest_subseq(string S, int k) { int n = S.size(); string ans = "" ; // Calculate maximum subsequence for // all possible min, max pair character // (which is equal to no of alphabet // minus k ) for ( int i = 0; i < 26 - k; i++) { // Curr minimum and maximum // character pair char min_char = 'a' + i; char max_char = min_char + k; string curr = "" ; // Flag to check if our current // subsequence have minimum/maximum // character in it bool min_char_exists = false , max_char_exists = false ; for ( int j = 0; j < n; j++) { // Include only those characters // which lies between minimum and // maximum character or equal if (S[j] >= min_char && S[j] <= max_char) { // Turn the flag true if // current character is // equal to min/max character if (S[j] == min_char) min_char_exists = true ; if (S[j] == max_char) max_char_exists = true ; curr += S[j]; } } // Check if max/min character exists // and length of current sting is // greater than previous calcualted // strings, save it as answer if (min_char_exists && max_char_exists && curr.size() > ans.size()) ans = curr; } return ans; } // Driver code int main() { string s = "daaaabbbadddddeeee" ; int k = 1; // Function call cout << longest_subseq(s, k); return 0; } |
Java
// Java code implementation for above approach import java.io.*; class GFG { // Function to find the longest subsequence with // difference equals to k. static String longest_subseq(String S, int k) { int n = S.length(); String ans = "" ; // Calculate maximum subsequence for all possible // min, max pair character (which is equal to no of // alphabet minus k) for ( int i = 0 ; i < 26 - k; i++) { // Curr minimum and maximum character pair char min_char = ( char )( 'a' + i); char max_char = ( char )(min_char + k); String curr = "" ; // Flag to check if our current subsequence have // minimum/maximum character in it boolean min_char_exists = false ; boolean max_char_exists = false ; for ( int j = 0 ; j < n; j++) { // Include only those characters which lies // between minimum and maximum character or // equal if (S.charAt(j) >= min_char && S.charAt(j) <= max_char) { // Turn the flag true if current // character is equal to min/max // character if (S.charAt(j) == min_char) min_char_exists = true ; if (S.charAt(j) == max_char) max_char_exists = true ; curr += S.charAt(j); } } // Check if max/min character exists and length // of current string is greater than previously // calculated strings, save it as answer if (min_char_exists && max_char_exists && curr.length() > ans.length()) ans = curr; } return ans; } public static void main(String[] args) { String s = "daaaabbbadddddeeee" ; int k = 1 ; // Function call System.out.println(longest_subseq(s, k)); } } // This code is contributed by lokesh. |
Python3
# Python3 code for above approach # Function to find the longest subsequence # with difference equals to k. def longest_subseq(S, k): n = len (S) ans = "" # Calculate maximum subsequence for # all possible min, max pair character # (which is equal to no of alphabet # minus k ) for i in range ( 26 - k): # Curr minimum and maximum # character pair min_char = chr ( ord ( 'a' ) + i) max_char = chr ( ord (min_char) + k) curr = "" # Flag to check if our current # subsequence have minimum/maximum # character in it min_char_exists = False max_char_exists = False for j in range (n): # Include only those characters # which lies between minimum and # maximum character or equal if (S[j] > = min_char and S[j] < = max_char): # Turn the flag true if # current character is # equal to min/max character if (S[j] = = min_char): min_char_exists = True if (S[j] = = max_char): max_char_exists = True curr + = S[j] # Check if max/min character exists # and length of current sting is # greater than previous calcualted # strings, save it as answer if (min_char_exists and max_char_exists and len (curr) > len (ans)): ans = curr return ans # Driver code if __name__ = = "__main__" : s = "daaaabbbadddddeeee" k = 1 # Function call print (longest_subseq(s, k)) # This code is contributed by # Tapesh(tapeshdua420) |
C#
// C# code implementation for above approach using System; public class GFG { // Function to find the longest subsequence with // difference equals to k. static string LongestSubseq( string S, int k) { int n = S.Length; string ans = "" ; // Calculate maximum subsequence for all possible // min, max pair character (which is equal to no of // alphabet minus k) for ( int i = 0; i < 26 - k; i++) { // Curr minimum and maximum character pair char min_char = ( char )( 'a' + i); char max_char = ( char )(min_char + k); string curr = "" ; // Flag to check if our current subsequence have // minimum/maximum character in it bool min_char_exists = false ; bool max_char_exists = false ; for ( int j = 0; j < n; j++) { // Include only those characters which lies // between minimum and maximum character or // equal if (S[j] >= min_char && S[j] <= max_char) { // Turn the flag true if current // character is equal to min/max // character if (S[j] == min_char) min_char_exists = true ; if (S[j] == max_char) max_char_exists = true ; curr += S[j]; } } // Check if max/min character exists and length // of current string is greater than previously // calculated strings, save it as answer if (min_char_exists && max_char_exists && curr.Length > ans.Length) ans = curr; } return ans; } static public void Main() { // Code string s = "daaaabbbadddddeeee" ; int k = 1; // Function call Console.WriteLine(LongestSubseq(s, k)); } } // This code is contributed by karthik. |
Javascript
// Javascript code for above approach // Function to find the longest subsequence // with difference equals to k. function longest_subseq(S, k) { let n = S.length; let ans = "" ; // Calculate maximum subsequence for // all possible min, max pair character // (which is equal to no of alphabet // minus k ) for (let i = 0; i < 26 - k; i++) { // Curr minimum and maximum // character pair let min_char = String.fromCharCode(97 + i); let max_char = String.fromCharCode(97 + i + k); let curr = "" ; // Flag to check if our current // subsequence have minimum/maximum // character in it let min_char_exists = false ; let max_char_exists = false ; for (let j = 0; j < n; j++) { // Include only those characters // which lies between minimum and // maximum character or equal if (S[j] >= min_char && S[j] <= max_char) { // Turn the flag true if // current character is // equal to min/max character if (S[j] === min_char) min_char_exists = true ; if (S[j] === max_char) max_char_exists = true ; curr += S[j]; } } // Check if max/min character exists // and length of current sting is // greater than previous calcualted // strings, save it as answer if (min_char_exists && max_char_exists && curr.length > ans.length) ans = curr; } return ans; } // Driver code let s = "daaaabbbadddddeeee" ; let k = 1; // Function call console.log(longest_subseq(s, k)); // This code is contributed by Pushpesh Raj. |
ddddddeeee
Time Complexity: O(n)
Auxiliary Space: O(n)