将一根弦分成三个回文的最佳解决方案，最早切割

Question

我在一次采访中被问到这个问题：

给定一个字符串 (1<=|s|<=10^5(，检查是否可以将其划分为三个回文。如果可能有多个答案，则输出最早进行切割的答案。如果没有答案，请打印"不可能"。

**Input:**
radarnoonlevel
aabab
abcdefg
**Output:**
radar noon level
a a bab   (Notice how a, aba, b is also an answer, but we will output the one with the earliest cuts)
Impossible

我能够给出一个蛮力解决方案，运行两个循环并检查每 3 个子字符串(0-i、i-j、j-end(的回文属性。这显然不是最佳的，但从那时起我就无法找到更好的解决方案。

我需要一种方法来检查如果我知道字符串的回文属性，那么如何从开头删除字符或在末尾添加一个字符可以为我提供新字符串的属性，而无需再次检查整个字符串。我正在考虑使用三张地图，其中每个字符键都映射到出现次数，但这也不会引导我做任何事情。

Answer 1

仍然是 O(n^2( 解决方案，但您可以将回文子字符串的结果存储在表中并使用它来获得答案。

vector<string> threePalindromicSubstrings(string word) {
int n = word.size();
vector<vector<bool>> dp (n,vector<bool>(n,false));
for(int i = 0 ; i < n ; ++i)
dp[i][i] = 1;

for(int l = 2 ; l <= n ; ++l){
for(int i = 0 ; i < n - l +1 ; ++i){
int j = i + l - 1;
if(l == 2)
dp[i][j] = (word[i] == word[j]);
else
dp[i][j] = (word[i] == word[j]) && (dp[i+1][j-1]);
}
}
vector<string> ans;
for(int i = 0 ; i < n - 2 ; ++i){
if(dp[0][i]) {
for(int j = i+1 ; j < n - 1 ; ++j){
if(dp[i+1][j] && dp[j+1][n-1]){
ans.push_back(word.substr(0,i + 1));
ans.push_back(word.substr(i+1,j-i));
ans.push_back(word.substr(j+1,n-j));
return ans;
}
}
}
}
if(ans.empty())
ans.push_back("Impossible");
return ans;
}