Maximize Palindrome Length From Subsequences LeetCode solution in C++

1
class Solution {
2
 public:
3
  // use to memoize recursive solution
4
  vector<vector<int>> v;
5

6
  /*
7
  boundary of both strings,
8
  l is length of concatenated string,
9
  ans is used to store final result
10
  */
11

12
  int boundary, l, ans;
13

14
  // Longest palindromic string
15
  int find(string &s, int i, int j) {
16
    // i->left, j->right
17
    // if left index is greater than right then return
18
    if (i > j) return 0;
19

20
    // if already calculated, return result
21
    if (v[i][j] != -1) return v[i][j];
22

23
    // if we are at stage where i==j,
24
    // means here single character
25
    // count it and increase left boundary and decrease right boundary
26
    if (i == j) {
27
      return v[i][j] = 1 + find(s, i + 1, j - 1);
28
    }
29

30
    // if two characters are same, count these two and
31
    // increase left boundary and decrease right boundary
32
    // and call function
33
    if (s[i] == s[j]) {
34
      int k = v[i][j] = 2 + find(s, i + 1, j - 1);
35

36
      /*
37

38
       if left character is from word1 and
39
       right character is from word2
40
       then store maximum result in ans
41

42
       NOTE: till (boundary-1) index s stored word1
43
       and from index (boundary) s stored word2
44

45
      */
46
      if (i < boundary && j >= boundary) {
47
        ans = max(ans, k);
48
      }
49
      return k;
50
    }
51

52
    // if characters are not same,
53
    // try both increase left index and make right index constent
54
    //  or make left constant or decrease right index
55
    //  and return max of both
56
    else {
57
      return v[i][j] = max(find(s, i + 1, j), find(s, i, j - 1));
58
    }
59
  }
60

61
  int longestPalindrome(string word1, string word2) {
62
    // store boundary of strings
63
    boundary = word1.size();
64

65
    // concatenate both strings
66
    word1 += word2;
67

68
    // find total length of string
69
    l = word1.length();
70

71
    // used to memoize solution
72
    v = vector<vector<int>>(l + 1, vector<int>(l + 1, -1));
73

74
    // call function
75
    int k = find(word1, 0, l - 1);
76

77
    // return final ans
78
    return ans;
79
  }
80
};