Given a string S of length N and an integer K, the task is to find the length of longest sub-sequence such that the difference between the ASCII values of adjacent characters in the subsequence is not more than K.
Examples:
Input: N = 7, K = 2, S = "afcbedg" Output: 4 Explanation: Longest special sequence present in "afcbedg" is a, c, b, d. It is special because |a - c| <= 2, |c - b| <= 2 and | b-d| <= 2 Input: N = 13, K = 3, S = "neveropen" Output: 7
Naive approach: A brute force solution is to generate all the possible subsequences of various lengths and compute the maximum length of the valid subsequence. The time complexity will be exponential.
Efficient Approach: An efficient approach is to use the concept Dynamic Programming
- Create an array dp of 0’s with size equal to length of string.
- Create a supporting array max_length with 0’s of size 26.
- Iterate the string character by character and for each character determine the upper and lower bounds.
- Iterate nested loop in the range of lower and upper bounds.
- Fill the dp array with the maximum value between current dp indices and current max_length indices+1.
- Fill the max_length array with the maximum value between current dp indices and current max_length indices.
- Longest sub sequence length is the maximum value in dp array.
- Let us consider an example:
input string s is “afcbedg” and k is 2
- for 1st iteration value of i is ‘a’ and range of j is (0, 2)
and current dp = [1, 0, 0, 0, 0, 0, 0]- for 2nd iteration value of i is ‘f’ and range of j is (3, 7)
and current dp = [1, 1, 0, 0, 0, 0, 0]- for 3rd iteration value of i is ‘c’ and range of j is (0, 4)
and current dp = [1, 1, 2, 0, 0, 0, 0]- for 4th iteration value of i is ‘b’ and range of j is (0, 3)
and current dp = [1, 1, 2, 3, 0, 0, 0]- for 5th iteration value of i is ‘e’ and range of j is (2, 6)
and current dp = [1, 1, 2, 3, 3, 0, 0]- for 6th iteration value of i is ‘d’ and range of j is (1, 5)
and current dp = [1, 1, 2, 3, 3, 4, 0]- for 7th iteration value of i is ‘g’ and range of j is (4, 8)
and current dp = [1, 1, 2, 3, 3, 4, 4]longest length is the maximum value in dp so maximum length is 4
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find// the longest Special Sequenceint longest_subseq(int n, int k, string s){ // Creating a list with // all 0's of size // equal to the length of string vector<int> dp(n, 0); // Supporting list with // all 0's of size 26 since // the given string consists // of only lower case alphabets int max_length[26] = {0}; for (int i = 0; i < n; i++) { // Converting the ascii value to // list indices int curr = s[i] - 'a'; // Determining the lower bound int lower = max(0, curr - k); // Determining the upper bound int upper = min(25, curr + k); // Filling the dp array with values for (int j = lower; j < upper + 1; j++) { dp[i] = max(dp[i], max_length[j] + 1); } //Filling the max_length array with max //length of subsequence till now max_length[curr] = max(dp[i], max_length[curr]); } int ans = 0; for(int i:dp) ans = max(i, ans); // return the max length of subsequence return ans;}// Driver Codeint main(){ string s = "neveropen"; int n = s.size(); int k = 3; cout << (longest_subseq(n, k, s)); return 0;}// This code is contributed by Mohit Kumar |
Java
// Java program for the above approachclass GFG{// Function to find// the longest Special Sequencestatic int longest_subseq(int n, int k, String s){ // Creating a list with // all 0's of size // equal to the length of String int []dp = new int[n]; // Supporting list with // all 0's of size 26 since // the given String consists // of only lower case alphabets int []max_length = new int[26]; for (int i = 0; i < n; i++) { // Converting the ascii value to // list indices int curr = s.charAt(i) - 'a'; // Determining the lower bound int lower = Math.max(0, curr - k); // Determining the upper bound int upper = Math.min(25, curr + k); // Filling the dp array with values for (int j = lower; j < upper + 1; j++) { dp[i] = Math.max(dp[i], max_length[j] + 1); } // Filling the max_length array with max // length of subsequence till now max_length[curr] = Math.max(dp[i], max_length[curr]); } int ans = 0; for(int i:dp) ans = Math.max(i, ans); // return the max length of subsequence return ans;}// Driver Codepublic static void main(String[] args){ String s = "neveropen"; int n = s.length(); int k = 3; System.out.print(longest_subseq(n, k, s));}}// This code is contributed by 29AjayKumar |
Python3
# Function to find # the longest Special Sequencedef longest_subseq(n, k, s): # Creating a list with # all 0's of size # equal to the length of string dp = [0] * n # Supporting list with # all 0's of size 26 since # the given string consists # of only lower case alphabets max_length = [0] * 26 for i in range(n): # Converting the ascii value to # list indices curr = ord(s[i]) - ord('a') # Determining the lower bound lower = max(0, curr - k) # Determining the upper bound upper = min(25, curr + k) # Filling the dp array with values for j in range(lower, upper + 1): dp[i] = max(dp[i], max_length[j]+1) # Filling the max_length array with max # length of subsequence till now max_length[curr] = max(dp[i], max_length[curr]) # return the max length of subsequence return max(dp)# driver codedef main(): s = "neveropen" n = len(s) k = 3 print(longest_subseq(n, k, s))main() |
C#
// C# program for the above approachusing System;class GFG{// Function to find// the longest Special Sequencestatic int longest_subseq(int n, int k, String s){ // Creating a list with // all 0's of size // equal to the length of String int []dp = new int[n]; // Supporting list with // all 0's of size 26 since // the given String consists // of only lower case alphabets int []max_length = new int[26]; for (int i = 0; i < n; i++) { // Converting the ascii value to // list indices int curr = s[i] - 'a'; // Determining the lower bound int lower = Math.Max(0, curr - k); // Determining the upper bound int upper = Math.Min(25, curr + k); // Filling the dp array with values for (int j = lower; j < upper + 1; j++) { dp[i] = Math.Max(dp[i], max_length[j] + 1); } // Filling the max_length array with max // length of subsequence till now max_length[curr] = Math.Max(dp[i], max_length[curr]); } int ans = 0; foreach(int i in dp) ans = Math.Max(i, ans); // return the max length of subsequence return ans;}// Driver Codepublic static void Main(String[] args){ String s = "neveropen"; int n = s.Length; int k = 3; Console.Write(longest_subseq(n, k, s));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to find// the longest Special Sequencefunction longest_subseq(n, k, s){ // Creating a list with // all 0's of size // equal to the length of String let dp = new Array(n); // Supporting list with // all 0's of size 26 since // the given String consists // of only lower case alphabets let max_length = new Array(26); for(let i = 0; i < 26; i++) { max_length[i] = 0; dp[i] = 0; } for (let i = 0; i < n; i++) { // Converting the ascii value to // list indices let curr = s[i].charCodeAt(0) - 'a'.charCodeAt(0); // Determining the lower bound let lower = Math.max(0, curr - k); // Determining the upper bound let upper = Math.min(25, curr + k); // Filling the dp array with values for (let j = lower; j < upper + 1; j++) { dp[i] = Math.max(dp[i], max_length[j] + 1); } // Filling the max_length array with max // length of subsequence till now max_length[curr] = Math.max(dp[i], max_length[curr]); } let ans = 0; ans = Math.max(...dp) // return the max length of subsequence return ans;}// Driver Codelet s = "neveropen";let n = s.length;let k = 3;document.write(longest_subseq(n, k, s));// This code is contributed by unknown2108</script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
