Number of ways to insert a character to increase the LCS by one | C # Program for Number of ways to insert a character to increase LCS by one ; Return the Number of ways to insert a character to increase the longest Common Subsequence by one ; Insert all positions of all characters in string B . ; longest Common Subsequence ; longest Common Subsequence from reverse ; inserting character between position i and i + 1 ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static readonly int MAX = 256 ; static int numberofways ( String A , String B , int N , int M ) { List < int > [ ] pos = new List < int > [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) pos [ i ] = new List < int > ( ) ; for ( int i = 0 ; i < M ; i ++ ) pos [ B [ i ] ] . Add ( i + 1 ) ; int [ , ] dpl = new int [ N + 2 , M + 2 ] ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = 1 ; j <= M ; j ++ ) { if ( A [ i - 1 ] == B [ j - 1 ] ) dpl [ i , j ] = dpl [ i - 1 , j - 1 ] + 1 ; else dpl [ i , j ] = Math . Max ( dpl [ i - 1 , j ] , dpl [ i , j - 1 ] ) ; } } int LCS = dpl [ N , M ] ; int [ , ] dpr = new int [ N + 2 , M + 2 ] ; for ( int i = N ; i >= 1 ; i -- ) { for ( int j = M ; j >= 1 ; j -- ) { if ( A [ i - 1 ] == B [ j - 1 ] ) dpr [ i , j ] = dpr [ i + 1 , j + 1 ] + 1 ; else dpr [ i , j ] = Math . Max ( dpr [ i + 1 , j ] , dpr [ i , j + 1 ] ) ; } } int ans = 0 ; for ( int i = 0 ; i <= N ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { foreach ( int x in pos [ j ] ) { if ( dpl [ i , x - 1 ] + dpr [ i + 1 , x + 1 ] == LCS ) { ans ++ ; break ; } } } } return ans ; } public static void Main ( String [ ] args ) { String A = " aa " , B = " baaa " ; int N = A . Length , M = B . Length ; Console . WriteLine ( numberofways ( A , B , N , M ) ) ; } }