Shortest Uncommon Subsequence | A dynamic programming based C # 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
using System ; class GFG { static readonly 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 ; Console . WriteLine ( " Length ▁ of ▁ shortest " + " subsequence ▁ is ▁ : ▁ " + shortestSeq ( S , T ) ) ; } }