To solve this problem, we need to determine the minimum number of characters to remove from a given string so that the remaining string becomes a palindrome. The key insight here is that the longest palindromic subsequence (LPS) of the string gives us the longest sequence of characters that can be kept (since it is a palindrome). The minimum number of deletions required is the length of the string minus the length of its LPS.
Approach
- Reverse the String: The LPS of a string is equivalent to the longest common subsequence (LCS) between the string and its reverse. This is because the LCS of a string and its reverse will be the longest sequence that appears in both, hence forming a palindrome.
- Compute LCS: Use dynamic programming to compute the length of the LCS between the original string and its reverse.
- Calculate Result: The minimum deletions are the length of the original string minus the length of the LCS (which is the LPS length).
Solution Code
s = input().strip()
rev_s = s[::-1]
n = len(s)
# Initialize DP table for LCS
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if s[i-1] == rev_s[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lps_length = dp[n][n]
print(n - lps_length)
Explanation
- Reverse the String: By reversing the string, we transform the problem of finding the LPS into finding the LCS between the original and reversed strings.
- Dynamic Programming Table: The DP table
dp[i][j]stores the length of the LCS of the firsticharacters of the original string and the firstjcharacters of the reversed string.- If the characters at positions
i-1(original) andj-1(reversed) are the same, we increment the value fromdp[i-1][j-1]. - If not, we take the maximum value from either
dp[i-1][j](ignoring the current character in the original string) ordp[i][j-1](ignoring the current character in the reversed string).
- If the characters at positions
- Result Calculation: The length of the LPS is the value at
dp[n][n](wherenis the length of the string). Subtracting this from the original length gives the minimum number of deletions needed.
This approach efficiently computes the result with a time complexity of O(n²) and space complexity of O(n²), which is feasible for the given problem constraints (string length up to 1000). For space optimization, we can reduce the space complexity to O(n) by using two rows (previous and current) instead of the full 2D table. However, the current solution is straightforward and works well for the given problem limits.
Space-Optimized Version: If you want to optimize space, here's the version using two rows:
s = input().strip()
rev_s = s[::-1]
n = len(s)
prev = [0] * (n + 1)
for i in range(1, n + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s[i-1] == rev_s[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
print(n - prev[n])
This version uses O(n) space, which is more efficient for larger strings. Both versions are correct and produce the same result. Choose the one that best fits your needs.


作者声明:本文包含人工智能生成内容。