Palindrome
Problem Statement Given a string S of length N (N 5000), find the minimum number of characters that must be inserted (at any positions) to make S a palindrome. Solution Approach Key Observation The minimum number of i...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Given a string $S$ of length $N$ ($N \le 5000$), find the minimum number of characters that must be inserted (at any positions) to make $S$ a palindrome.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution Approach
Key Observation
The minimum number of insertions equals: \[ N - \mathrm{LPS}(S), \] where $\mathrm{LPS}(S)$ is the length of the longest palindromic subsequence of $S$.
Proof.
Every palindrome of length $\ell$ that contains $S$ as a subsequence has length $\ge 2N - \ell$ where $\ell$ is the longest palindromic subsequence of $S$ (the LPS characters stay in place; each non-LPS character requires one insertion to create its mirror). The minimum palindrome length achievable is $2N - \mathrm{LPS}(S)$, requiring $N - \mathrm{LPS}(S)$ insertions.
Reduction to LCS
The longest palindromic subsequence of $S$ equals the longest common subsequence of $S$ and its reverse $S^R$: \[ \mathrm{LPS}(S) = \mathrm{LCS}(S, S^R). \]
Space-Optimized LCS
Standard LCS uses an $N \times N$ table, which for $N = 5000$ is 100 MB (too large). Since each row of the LCS table depends only on the previous row, we use a rolling two-row approach, reducing space to $O(N)$.
C++ Solution
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
scanf("%d", &N);
char S[5001];
scanf("%s", S);
// Reverse of S
char T[5001];
for (int i = 0; i < N; i++)
T[i] = S[N - 1 - i];
T[N] = '\0';
// LCS(S, T) with O(N) space
vector<int> prev(N + 1, 0), curr(N + 1, 0);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (S[i - 1] == T[j - 1]) {
curr[j] = prev[j - 1] + 1;
} else {
curr[j] = max(prev[j], curr[j - 1]);
}
}
swap(prev, curr);
fill(curr.begin(), curr.end(), 0);
}
int lps = prev[N];
printf("%d\n", N - lps);
return 0;
}Alternative: Direct Interval DP
Define $\mathrm{dp}[i][j]$ = minimum insertions to make $S[i \ldots j]$ a palindrome.
Base: $\mathrm{dp}[i][i] = 0$, $\mathrm{dp}[i][i{-}1] = 0$.
Transition: \[ dp[i][j] =
\]
This also runs in $O(N^2)$ time. With a rolling-array technique (keeping only three gap-lengths at a time: current, previous, and two-back), the space reduces to $O(N)$.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
scanf("%d", &N);
char S[5001];
scanf("%s", S);
// Rolling arrays for gap-based interval DP
// prev2[i] = dp for gap-2 starting at i
// dp[i] = dp for gap-1 starting at i
// ndp[i] = dp for current gap starting at i
vector<int> dp(N, 0), ndp(N, 0), prev2(N, 0);
// gap = 1 (length-2 substrings)
for (int i = 0; i + 1 < N; i++)
ndp[i] = (S[i] == S[i + 1]) ? 0 : 1;
if (N >= 2) {
swap(prev2, dp); // prev2 = gap-0 results (all 0)
swap(dp, ndp); // dp = gap-1 results
}
for (int gap = 2; gap < N; gap++) {
for (int i = 0; i + gap < N; i++) {
int j = i + gap;
if (S[i] == S[j])
ndp[i] = prev2[i + 1]; // dp[i+1][j-1]
else
ndp[i] = min(dp[i + 1], dp[i]) + 1;
}
swap(prev2, dp);
swap(dp, ndp);
}
printf("%d\n", dp[0]);
return 0;
}Complexity Analysis
Time complexity: $O(N^2)$ for both approaches.
Space complexity: $O(N)$ with the rolling-array optimization.
Code
C++ solution used for this page.
// IOI 2000 - Palindrome
// Find minimum character insertions to make string S a palindrome.
// Answer = N - LPS(S), where LPS = longest palindromic subsequence.
// LPS(S) = LCS(S, reverse(S)), computed with O(N) space rolling array.
// Complexity: O(N^2) time, O(N) space.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
string S;
cin >> S;
// Edge case: empty or single character
if (N <= 1) {
cout << 0 << "\n";
return 0;
}
// LPS(S) = LCS(S, reverse(S))
string T(S.rbegin(), S.rend());
// LCS with O(N) space using rolling arrays
vector<int> prev(N + 1, 0), curr(N + 1, 0);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (S[i - 1] == T[j - 1]) {
curr[j] = prev[j - 1] + 1;
} else {
curr[j] = max(prev[j], curr[j - 1]);
}
}
swap(prev, curr);
fill(curr.begin(), curr.end(), 0);
}
int lps = prev[N];
cout << N - lps << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.