### mkmeden's blog

By mkmeden, history, 18 months ago,

https://www.hackerrank.com/challenges/tutzki-and-lcs/problem

I ve been trying to solve this for hours and could'nt find any understandable online solution, Can anyone explain the logic and code behind this problem.

• +6

 » 18 months ago, # |   +1 You just calculate the $LCS$ as you do. Let $dp1[i][j]$ denotes the $LCS$ of the suffix starting from $ith$ and $jth$ index of string $a$ and $b$ respectively. And $dp2[i][j]$denotes the $LCS$ of the prefix till $ith$ and $jth$ index of string $a$ and $b$ respectively. Now assume we are adding a character before $ith$ index of string $a$ to match it with $jth$ index of string $b$. Think of the condition for this pair of indexes to contribute to the answer. Condition$dp1[i][j+1] + dp2[i-1][j-1] == LCS$If we implement that condition directly, then it will overcount. Think why is it so? ReasonOnly the different number of final $a$ string formed matters. So, there might be a possibility that you are counting the same character at an index multiple times because that character may appear at different positions in string $b$. How to fix it?You can create a $vis[i][j]$ array to mark $1$ if you have placed $jth$ character at index $i$, and then count the final answer using the number of elements that are marked $1$ in the $vis$ array. Code#include #define ll int #define f(i,a,b) for(ll i=a;i=b;i--) #define sc(a) scanf("%lld",&a) #define pf printf #define sz(a) (int)(a.size()) #define psf push_front #define ppf pop_front #define ppb pop_back #define pb push_back #define pq priority_queue #define all(s) s.begin(),s.end() #define sp(a) setprecision(a) #define rz resize #define ld long double #define inf (ll)1e18 #define ub upper_bound #define lb lower_bound #define bs binary_search #define eb emplace_back const double pi = acos(-1); ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;} ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;} using namespace std; ll dp[5003][5003],rdp[5003][5003],n,m; string a,b; ll fn(ll i, ll j) { if(i>=n || j>=m) return 0; ll &ans=dp[i][j]; if(ans==-1) { ans=0; if(a[i]==b[j]) ans=1+fn(i+1,j+1); else ans=max({ans,fn(i+1,j),fn(i,j+1)}); } return ans; } ll rfn(ll i, ll j) { if(i<0 || j<0) return 0; ll &ans=rdp[i][j]; if(ans==-1) { ans=0; if(a[i]==b[j]) ans=1+rfn(i-1,j-1); else ans=max({ans,rfn(i-1,j),rfn(i,j-1)}); } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int z=1; f(i,1,z+1) { cin>>a>>b; n=sz(a),m=sz(b); memset(dp,-1,sizeof(dp)),memset(rdp,-1,sizeof(rdp)); ll ans=0,lcs=fn(0,0); vector > vis(n+69,vector (269)); f(i,0,n+1) { f(j,0,m) { if(rfn(i-1,j-1)+fn(i,j+1)==lcs) vis[i][(int)b[j]]=1; } } f(i,0,n+1) { f(j,0,269) { if(vis[i][j]) ans++; } } cout<
•  » » 18 months ago, # ^ | ← Rev. 2 →   +1 Thank you so much brother. I understood your explanation. My Code#include using namespace std; int solve(string a, string b) { int n = a.length(); int m = b.length(); vector>dp1(n+2 , vector(m+2)); vector>dp2(n+2 , vector(m+2)); for(int i = 1 ; i<=n ; i++) for(int j =1 ; j<=m ; j++) dp1[i][j] = max(max(dp1[i-1][j], dp1[i][j-1]), dp1[i-1][j-1] + (a[i-1]==b[j-1])); for(int i = n ; i>=1 ; i--) for(int j =m ; j>=1 ; j--) dp2[i][j] = max(max(dp2[i+1][j], dp2[i][j+1]), dp2[i+1][j+1] + (a[i-1]==b[j-1])); int ctr= 0 ; for(int i =0 ; i<=n ; i++) { sethash; for(int j= 1 ; j<=m; j++) { if( hash.find(b[j-1]) == hash.end() && dp1[i][j-1] + dp2[i+1][j+1]==dp1[n][m]) { ctr++; hash.insert(b[j-1]); } } } return ctr ; } int main() { string a; getline(cin, a); string b; getline(cin, b); int result = solve(a, b); cout << result << "\n"; }