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 stringint 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 Codeint main(){ string s = "fdryutiaghfse"; cout << lisOtimised(s); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int mn = -2147483648; // Function to find length of longest// increasing subsequence in a stringstatic 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 Codepublic 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 stringdef 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 Codeif __name__ == '__main__': s = "fdryutiaghfse" print (lisOtimised(s))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static int mn = -2147483648; // Function to find length of longest// increasing subsequence in a stringstatic 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 Codepublic 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 stringfunction 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)
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!
… [Trackback]
[…] Here you will find 48532 more Information to that Topic: geeksforgeeks.org/length-of-longest-increasing-subsequence-in-a-string/ […]
… [Trackback]
[…] There you can find 95602 more Information on that Topic: geeksforgeeks.org/length-of-longest-increasing-subsequence-in-a-string/ […]