Shortest Uncommon Subsequence | A dynamic programming based Java program to find shortest uncommon subsequence . ; Returns length of shortest common subsequence ; declaring 2D array of m + 1 rows and n + 1 columns dynamically ; T string is empty ; S string is empty ; char not present in T ; Driver code
class GFG { static final int MAX = 1005 ; static int shortestSeq ( char [ ] S , char [ ] T ) { int m = S . length , n = T . length ; int dp [ ] [ ] = new int [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { dp [ i ] [ 0 ] = 1 ; } for ( int i = 0 ; i <= n ; i ++ ) { dp [ 0 ] [ i ] = MAX ; } for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { char ch = S [ i - 1 ] ; int k ; for ( k = j - 1 ; k >= 0 ; k -- ) { if ( T [ k ] == ch ) { break ; } } if ( k == - 1 ) { dp [ i ] [ j ] = 1 ; } else { dp [ i ] [ j ] = Math . min ( dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ k ] + 1 ) ; } } } int ans = dp [ m ] [ n ] ; if ( ans >= MAX ) { ans = - 1 ; } return ans ; } public static void main ( String [ ] args ) { char S [ ] = " babab " . toCharArray ( ) ; char T [ ] = " babba " . toCharArray ( ) ; int m = S . length , n = T . length ; System . out . println ( " Length ▁ of ▁ shortest " + " subsequence ▁ is ▁ : ▁ " + shortestSeq ( S , T ) ) ; } }