knearpalindromic

Knearpalindromic is a term used to describe a property of a string or sequence relative to palindromes, parameterized by a nonnegative integer k. It denotes how close the string is to being a palindrome when allowing up to k changes.

Formal definition: Let s be a string of length n over an alphabet. s is knearpalindromic with parameter k if there exists a palindrome p of length n such that the Hamming distance between s and p is at most k. Equivalently, the number of mismatched mirrored pairs (i, n-1-i) across the center does not exceed k. Variants exist that allow edits beyond substitutions, such as insertions and deletions, but the common version uses substitutions only.

Recognition and computation: To test knearpalindromicity with fixed k, count the number of i in 0 to floor((n-1)/2) for which s[i] != s[n-1-i]. If that count is at most k, the string is knearpalindromic for that k. The check is linear in the string length. For more general notions that permit insertions and deletions, the problem becomes a shortest-edit-to-palindrome problem and is typically addressed with dynamic programming, often with O(n^2) time complexity.

Examples: The string "abca" is knearpalindromic with k = 1 because the only mismatched pair is s[1] and s[2]. The string "abcd" has two mismatched pairs, so it is knearpalindromic with k = 2 (but not with k = 1).

See also: palindrome, k-palindrome, near-palindrome. Knearpalindromic sits within discussions of string similarity and palindrome-constrained problems in algorithm design and coding contexts.