INQU2003 - Editorial

editorial
,
1

PROBLEM LINK:
link for the question

DIFFICULTY:
Medium

PREREQUISITES:
Dynamic Programming

EXPLANATION:
In solution we will have 4 strings str1, str2, str3, str4 such that str1+str2+str3+str4 is a palindrome. Since |str1| = |str4| and |str2| = |str3| so we can say str1=reverse(str4) and str2=reverse(str3).

To approach the problem we will first reverse the first string. Now we will find substrings str1,str2 from first string and str3,str4 from second string and since we used reverse of first string we can say that str1 = str3 and str2 = str4.

We can use dynamic programming to solve this problem. We can divide the question in 3 phases -

  1. We are currently choosing characters for str1 and str3.
  2. We have completed phase1 and not started phase3 yet.
  3. We are currently choosing characters for str2 and str4.

The dp will be in the form dp(i,j,k) where i is the index for string1 and j is the index for string2 and k is the phase.

TIME COMPLEXITY:
Time complexity per testcase is O(N*N).

SOLUTION:

Editorialist's Solution 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pii;
typedef tree<ll, null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define debug1(x) cerr<<#x<<" : "<<(x)<<endl
#define debug2(x,y) cerr<<#x<<" : "<<(x)<<" "<<#y<<" : "<<(y)<<endl
#define debug3(x,y,z) cerr<<#x<<" : "<<(x)<<" "<<#y<<" : "<<(y)<<" "<<#z<<" : "<<(z)<<endl
#define fastt ios_base::sync_with_stdio(false); cin.tie(NULL) ; cout.tie(NULL)
const ll modd=1e9+7;
const ll inff=1e18;
/*-----------------------------------------------------------------------------------------------*/
int main(){
  fastt;
  ll tc;
  cin >> tc;
  while(tc--){
      string str1 , str2;
      cin >> str1 >> str2;
      reverse(str1.begin(),str1.end());
      ll len1 = (ll)str1.length();
      ll len2 = (ll)str2.length();
      ll dp[len1+1][len2+1][3] , dp1[len1+1][len2+1];
      memset(dp,0,sizeof(dp));
      memset(dp1,0,sizeof(dp1));
      for(ll i = 1; i <= len1; i++){
          for(ll j = 1; j <= len2; j++){
              if(str1[i-1] == str2[j-1]){
                dp[i][j][0] = max(dp[i][j][0] , dp[i-1][j-1][0] + 1);
                dp[i][j][2] = max({dp[i][j][2] , dp[i-1][j-1][2] + 1 , dp[i-1][j-1][1] + 1});
              }
              dp[i][j][1] = max({dp[i-1][j][1] , dp[i][j-1][1] , dp[i][j][0]});
          }
      }
      ll ans = 0;
      for(ll i = 1; i <= len1; i++){
        for(ll j = 1; j <= len2; j++)
          ans = max({ans , dp[i][j][0] , dp[i][j][2]});
      }
      cout << 2 * ans << '\n';
  }
  return 0;
}