Length of longest increasing subsequence in a string

0 0 5 minutes read

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 i^th 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:

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 zambiatek!