1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
function longestPalindrome(s: string, t: string): number {
let ans = 0;
const memo = new Map<string, number>();
const dps = lpsStart(s);
const dpt = lpsEnd(t);
// Check single string palindromes
for (const length of dps) {
ans = Math.max(ans, length);
}
for (const length of dpt) {
ans = Math.max(ans, length);
}
// Find cross-string palindromes
find(dps, dpt, s, t, s.length - 1, 0, memo, ans);
return ans;
}
function lpsStart(s: string): number[] {
const n = s.length;
const res = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
// Odd length palindromes
let len = expand(s, i, i);
if (i - len >= 0) {
res[i - len] = Math.max(res[i - len], len * 2 + 1);
}
// Even length palindromes
len = expand(s, i, i + 1);
if (len >= 0 && i - len >= 0) {
res[i - len] = Math.max(res[i - len], len * 2 + 2);
}
}
return res;
}
function lpsEnd(s: string): number[] {
const n = s.length;
const res = new Array(n).fill(1);
for (let i = 0; i < n; i++) {
// Odd length palindromes
let len = expand(s, i, i);
if (i + len < n) {
res[i + len] = Math.max(res[i + len], len * 2 + 1);
}
// Even length palindromes
len = expand(s, i - 1, i);
if (len >= 0 && i + len < n) {
res[i + len] = Math.max(res[i + len], len * 2 + 2);
}
}
return res;
}
function expand(s: string, l: number, r: number): number {
let res = 0;
while (l >= 0 && r < s.length && s[l] === s[r]) {
res++;
l--;
r++;
}
return res - 1;
}
function find(
dps: number[], dpt: number[], s: string, t: string,
i: number, j: number, memo: Map<string, number>, ans: number
): number {
if (i < 0 || j >= t.length) return 0;
const key = `${i},${j}`;
if (memo.has(key)) return memo.get(key)!;
let res = 0;
if (s[i] === t[j]) {
res = 2 + find(dps, dpt, s, t, i - 1, j + 1, memo, ans);
}
// Update answer with current palindrome + extensions
ans = Math.max(ans, res + (j > 0 ? dpt[j - 1] : 0));
ans = Math.max(ans, res + (i < s.length - 1 ? dps[i + 1] : 0));
// Continue exploring
find(dps, dpt, s, t, i - 1, j, memo, ans);
find(dps, dpt, s, t, i, j + 1, memo, ans);
memo.set(key, res);
return res;
}
|