Length of longest increasing subsequence in a string
Given a string S, the task is to find the length of the longest increasing subsequence present in the given string.
A sequence of characters placed in increasing order of their ASCII values is called an increasing sequence.
Examples:
Input: S = “abcfgffs”
Output: 6
Explanation: Subsequence “abcfgs” is the longest increasing subsequence present in the string. Therefore, the length of the longest increasing subsequence is 6.Input: S = “aaabac”
Output: 3
Approach: The idea is to use Dynamic Programming. Follow the steps given below to solve the problem:
- Initialize an array, say dp[] of size 26, to store at every ith index, the length of the longest increasing subsequence having (‘a’ + i)th character as the last character in the subsequence.
- Initialize variable, say lis, to store the length of the required subsequence.
- Iterate over each character of the string S.
- For every character encountered, i.e. S[i] – ‘a’, check for all characters, say j, with ASCII values smaller than that of the current character.
- Initialize a variable, say curr, to store the length of LIS ending with current character.
- Update curr with max(curr, dp[j]).
- Update length of the LIS, say lis, with max(lis, curr + 1).
- Update dp[S[i] – ‘a’] with max of d[S[i] – ‘a’] and curr.
- Finally, print the value of lis as the required length of LIS.
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 length of longest // increasing subsequence in a string int lisOtimised(string s) { // Stores at every i-th index, the // length of the longest increasing // subsequence ending with character i int dp[30] = { 0 }; // Size of string int N = s.size(); // Stores the length of LIS int lis = INT_MIN; // Iterate over each // character of the string for ( int i = 0; i < N; i++) { // Store position of the // current character int val = s[i] - 'a' ; // Stores the length of LIS // ending with current character int curr = 0; // Check for all characters // less than current character for ( int j = 0; j < val; j++) { curr = max(curr, dp[j]); } // Include current character curr++; // Update length of longest // increasing subsequence lis = max(lis, curr); // Updating LIS for current character dp[val] = max(dp[val], curr); } // Return the length of LIS return lis; } // Driver Code int main() { string s = "fdryutiaghfse" ; cout << lisOtimised(s); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static int mn = - 2147483648 ; // Function to find length of longest // increasing subsequence in a string static int lisOtimised(String s) { // Stores at every i-th index, the // length of the longest increasing // subsequence ending with character i int []dp = new int [ 30 ]; Arrays.fill(dp, 0 ); // Size of string int N = s.length(); // Stores the length of LIS int lis = mn; // Iterate over each // character of the string for ( int i = 0 ; i < N; i++) { // Store position of the // current character int val = ( int )s.charAt(i) - 97 ; // Stores the length of LIS // ending with current character int curr = 0 ; // Check for all characters // less than current character for ( int j = 0 ; j < val; j++) { curr = Math.max(curr, dp[j]); } // Include current character curr++; // Update length of longest // increasing subsequence lis = Math.max(lis, curr); // Updating LIS for current character dp[val] = Math.max(dp[val], curr); } // Return the length of LIS return lis; } // Driver Code public static void main(String[] args) { String s = "fdryutiaghfse" ; System.out.print(lisOtimised(s)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to find length of longest # increasing subsequence in a string def lisOtimised(s): # Stores at every i-th index, the # length of the longest increasing # subsequence ending with character i dp = [ 0 ] * 30 # Size of string N = len (s) # Stores the length of LIS lis = - 10 * * 9 # Iterate over each # character of the string for i in range (N): # Store position of the # current character val = ord (s[i]) - ord ( 'a' ) # Stores the length of LIS # ending with current character curr = 0 # Check for all characters # less than current character for j in range (val): curr = max (curr, dp[j]) # Include current character curr + = 1 # Update length of longest # increasing subsequence lis = max (lis, curr) # Updating LIS for current character dp[val] = max (dp[val], curr) # Return the length of LIS return lis # Driver Code if __name__ = = '__main__' : s = "fdryutiaghfse" print (lisOtimised(s)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static int mn = -2147483648; // Function to find length of longest // increasing subsequence in a string static int lisOtimised( string s) { // Stores at every i-th index, the // length of the longest increasing // subsequence ending with character i int []dp = new int [30]; Array.Clear(dp, 0, 30); // Size of string int N = s.Length; // Stores the length of LIS int lis = mn; // Iterate over each // character of the string for ( int i = 0; i < N; i++) { // Store position of the // current character int val = ( int )s[i] - 97; // Stores the length of LIS // ending with current character int curr = 0; // Check for all characters // less than current character for ( int j = 0; j < val; j++) { curr = Math.Max(curr, dp[j]); } // Include current character curr++; // Update length of longest // increasing subsequence lis = Math.Max(lis, curr); // Updating LIS for current character dp[val] = Math.Max(dp[val], curr); } // Return the length of LIS return lis; } // Driver Code public static void Main() { string s = "fdryutiaghfse" ; Console.Write(lisOtimised(s)); } } // This code is contributed by SURENDRA_GAANGWAR. |
Javascript
<script> // JavaScript program for the above approach // Function to find length of longest // increasing subsequence in a string function lisOtimised( s) { // Stores at every i-th index, the // length of the longest increasing // subsequence ending with character i let dp = new Array(30).fill(0); // Size of string let N = s.length; // Stores the length of LIS let lis = Number.MIN_VALUE; // Iterate over each // character of the string for (let i = 0; i < N; i++) { // Store position of the // current character let val = s.charCodeAt(i) - 'a' .charCodeAt(0); // Stores the length of LIS // ending with current character let curr = 0; // Check for all characters // less than current character for (let j = 0; j < val; j++) { curr = Math.max(curr, dp[j]); } // Include current character curr++; // Update length of longest // increasing subsequence lis = Math.max(lis, curr); // Updating LIS for current character dp[val] = Math.max(dp[val], curr); } // Return the length of LIS return lis; } // Driver Code let s = "fdryutiaghfse" ; document.write(lisOtimised(s)); </script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)