Find the longest subsequence of a string that is a substring of another string | Java program for the above approach ; Function to find the longest subsequence that matches with the substring of other string ; Stores the lengths of strings X and Y ; Create a matrix ; Initialize the matrix ; Fill all the remaining rows ; If the characters are equal ; If not equal , then just move to next in subsequence string ; Find maximum length of the longest subsequence matching substring of other string ; Iterate through the last row of matrix ; Store the required string ; Backtrack from the cell ; If equal , then add the character to res string ; Return the required string ; Driver Code
class GFG { public static String longestSubsequence ( String X , String Y ) { int n = X . length ( ) ; int m = Y . length ( ) ; int [ ] [ ] mat = new int [ n + 1 ] [ m + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < m + 1 ; j ++ ) { if ( i == 0 j == 0 ) mat [ i ] [ j ] = 0 ; } } for ( int i = 1 ; i < n + 1 ; i ++ ) { for ( int j = 1 ; j < m + 1 ; j ++ ) { if ( X . charAt ( i - 1 ) == Y . charAt ( j - 1 ) ) { mat [ i ] [ j ] = 1 + mat [ i - 1 ] [ j - 1 ] ; } else { mat [ i ] [ j ] = mat [ i - 1 ] [ j ] ; } } } int len = 0 , col = 0 ; for ( int i = 0 ; i < m + 1 ; i ++ ) { if ( mat [ n ] [ i ] > len ) { len = mat [ n ] [ i ] ; col = i ; } } String res = " " ; int i = n ; int j = col ; while ( len > 0 ) { if ( X . charAt ( i - 1 ) == Y . charAt ( j - 1 ) ) { res = X . charAt ( i - 1 ) + res ; i -- ; j -- ; len -- ; } else { i -- ; } } return res ; } public static void main ( String args [ ] ) { String X = " ABCD " ; String Y = " ACDBDCD " ; System . out . println ( longestSubsequence ( X , Y ) ) ; } }