Count ways to increase LCS length of two strings by one | C # program to get number of ways to increase LCS by 1 ; Method returns total ways to increase LCS length by 1 ; Fill positions of each character in vector ; Initializing 2D array by 0 values ; Filling LCS array for prefix substrings ; Filling LCS array for suffix substrings ; Looping for all possible insertion positions in first string ; Trying all possible lower case characters ; Now for each character , loop over same character positions in second string ; If both , left and right substrings make total LCS then increase result by 1 ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int M = 26 ; static int waysToIncreaseLCSBy1 ( String str1 , String str2 ) { int m = str1 . Length , n = str2 . Length ; List < int > [ ] position = new List < int > [ M ] ; for ( int i = 0 ; i < M ; i ++ ) position [ i ] = new List < int > ( ) ; for ( int i = 1 ; i <= n ; i ++ ) position [ str2 [ i - 1 ] - ' a ' ] . Add ( i ) ; int [ , ] lcsl = new int [ m + 2 , n + 2 ] ; int [ , ] lcsr = new int [ m + 2 , n + 2 ] ; for ( int i = 0 ; i <= m + 1 ; i ++ ) for ( int j = 0 ; j <= n + 1 ; j ++ ) lcsl [ i , j ] = lcsr [ i , j ] = 0 ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { if ( str1 [ i - 1 ] == str2 [ j - 1 ] ) lcsl [ i , j ] = 1 + lcsl [ i - 1 , j - 1 ] ; else lcsl [ i , j ] = Math . Max ( lcsl [ i - 1 , j ] , lcsl [ i , j - 1 ] ) ; } } for ( int i = m ; i >= 1 ; i -- ) { for ( int j = n ; j >= 1 ; j -- ) { if ( str1 [ i - 1 ] == str2 [ j - 1 ] ) lcsr [ i , j ] = 1 + lcsr [ i + 1 , j + 1 ] ; else lcsr [ i , j ] = Math . Max ( lcsr [ i + 1 , j ] , lcsr [ i , j + 1 ] ) ; } } int ways = 0 ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int d = 0 ; d < 26 ; d ++ ) { for ( int j = 0 ; j < position [ d ] . Count ; j ++ ) { int p = position [ d ] [ j ] ; if ( lcsl [ i , p - 1 ] + lcsr [ i + 1 , p + 1 ] == lcsl [ m , n ] ) ways ++ ; } } } return ways ; } public static void Main ( String [ ] args ) { String str1 = " abcabc " ; String str2 = " abcd " ; Console . WriteLine ( waysToIncreaseLCSBy1 ( str1 , str2 ) ) ; } }