kpalindrome

A k-palindrome is a string that can be transformed into a palindrome by deleting at most k characters. In this sense, the property is about how far a given string is from being a palindrome under deletions.

Equivalently, a string s is a k-palindrome if there exists a subsequence of s that is a palindrome of length at least |s| − k. Another common formulation is that the minimum number of deletions required to make s a palindrome is at most k. The notion is monotone: if s is a k-palindrome, it is also a j-palindrome for any j greater than or equal to k.

A useful relation for computation is that the minimum deletions to make s a palindrome equals n − LPS(s), where n is the length of s and LPS(s) is the length of the longest palindromic subsequence of s. Hence s is a k-palindrome precisely when LPS(s) ≥ n − k.

Dynamic programming provides practical algorithms. One approach computes LPS for all substrings, giving O(n^2) time and O(n^2) space. A space-optimized variant can achieve O(n) space with careful iteration. Alternatively, a direct DP computes the minimum deletions dp[i][j] for the substring s[i..j], with recurrence:

- if s[i] == s[j], dp[i][j] = dp[i+1][j−1];

- else, dp[i][j] = 1 + min(dp[i+1][j], dp[i][j−1]).

The answer is dp[0][n−1].

Variants of the definition may permit insertions as well as deletions, or focus on similar measures of distance to palindromicity. The concept is used in string analysis, competitive programming, and bioinformatics to assess how far a sequence is from being palindromic.

Examples: s = "abbda" has n = 5 and LPS length 4, so it is a 1-palindrome. s = "abcdef" has LPS length 1, so it is a 5-palindrome.