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: abcde

Input: 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:

Time Complexity: O(n)
Auxiliary Space: O(n)

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: abcde

Input: 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:

Time Complexity: O(n)
Auxiliary Space: O(n)