PROBLEM LINK:
Editorialist: Karan Aggarwal
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Longest Common subsequence, Dynamic Programming.
PROBLEM:
Given 3 strings A,B,C of length N each, (N<=450), tell the minimum number of characters we need to remove from them, to make them equal. In other words, find the longest common subsequence of A,B and C. There can be upto 13 test-cases.
EXPLANATION:
Similar to LCS in 2 string, we can maintain a DP(i,j,k) which is equal to the length of the LCS in A[0…i] and B[0…j] and C[0…k].
DP(i,j,k) = 1 + DP(i-1,j-1,k-1) , if A[i]=B[j]=C[k]
else max( DP(i-1,j,k,) , DP(i,j-1,k,) , DP(i,j,k-1))
Complexity O(N^3) per test case.