Given the palindrome string, how can we convert it to a non-palindrome by removing a few more characters from it?

Question

Given the palindrome string, how can we convert it to a non-palindrome by removing a few more characters from it?

For example, if the string is "b99b". Then we can do it in 6 ways,

i) Delete the 1st character: "99b"
ii) Delete 1st, 2nd characters: "9b"
iii) Delete 1st, 3rd characters: "9b"
iv) Delete 2nd, 4th characters: "b9"
v) Delete 3rd, 4th characters: "b9"
vi) Delete the 4th character: "b99"

How to approach this?

PS: Two methods are considered different if i exists, so the character in the index i is deleted in one way and not deleted in the other.

Answer 1

There is an O(n 2 ) dynamic programming algorithm for counting the number of palindromic subsequences of a string; you can use this to count the number of non-palindromic subsequences by subtracting the number of palindromic subsequences from the number of subsequences (which is just 2 ⁿ ).

This algorithm counts subsequences by criterion in the OP; two subsequences are considered different if there is a difference in the list of indices used to select the elements, even if the resulting subsequences have the same elements.

To count the palindromic subsequences, we create an account based on the intervals of the sequence. In particular, we define:

S i,j = substring S starting at index i and ending at index j (inclusive)

P i,j = number of palindromic subsequences S i,j

Now each singleton interval is a palindrome, therefore:

P i,i = 1 P i,i = 1 for all i < n

If the substring does not start and does not end with the same element (i.e., S i ≠ S j ), then palindromic subsequences consist of:

• Those that contain S i but do not contain S j

• Those that contain S j but do not contain S i

• Those that contain neither S i nor S j

Now notice that P i,j-1 contains both the first and third set of subsequences, and P i+1,j includes both the second and third set; P i+1,j-1 is exactly the third set. Hence:

P i,j = P i+1,j + P i,j-1 − P i+1,j-1 P i,j = P i+1,j + P i,j-1 − P i+1,j-1 if S i ≠ S j

But what if S i = S j S i = S j ? In this case, we must add palindromes consisting of S i , followed by the palindrome of the subsequence of S i+1,j-1 , followed by S j , as well as the palindrome subsequence, consisting only of the starting and ending characters. (Technically, an empty sequence is a palindrome, but we don’t count it here.) The number of subsequences that we add is P _{i + 1, j-1} & plus; 1, which cancels the deductible double count in the above equation. So:

P i,j = P i+1,j + P i,j-1 + 1 P i,j = P i+1,j + P i,j-1 + 1 if S i = S j S i = S j .

To save space, we can actually calculate P i,i+k for 0 ≤ i < |S|-k to increase the values ​​of k ; we need to save only two of these vectors to get the final result P _{0, | S | -1} .

---

EDIT

Here is a small python program; the first calculates the number of palindromic subsequences, as described above, and the driver calculates the number of non-palindromic subsequences (i.e. the number of ways to remove zero or more elements and create a non-palindrome, if the original sequence is a palindrome, then this is the number of ways to remove one or more elements.)

 # Count the palindromic subsequences of s def pcount(s): length = len(s) p0 = [0] * (length + 1) p1 = [1] * length for l in range(1, length): for i in range(length - l): p0[i] = p1[i] if s[i] == s[i + l]: p1[i] += p1[i+1] + 1 else: p1[i] += p1[i+1] - p0[i+1] # The "+ 1" is to account for the empty sequence, which is a palindrome. return p1[0] + 1 # Count the non-palindromic subsequences of s def npcount(s): return 2**len(s) - pcount(s) 

Answer 2

This is not a complete answer, just a suggestion.

I would count the number of ways to delete one or more characters and save the string with a palindrome. then subtract this from the total number of ways to change the line.

The most obvious way to change the palindrome and save it in the palindrome is to remove the i'th and (ni)'th characters (n is the length of the string). There are 2^(n/2) ways you can do this.

the problem with this approach is that it assumes that only a symmetric modification can contain a palindrome string, you need to find a way to handle cases like "aaaa" where any modification will still result in a palindrome.

Answer 3

Brute force with memoization is pretty simple:

 numWays(str): return 0 if str is empty return memo[str] if it exists memo[str] = numWays(str - firstChar) + numWays(str - secondChar) + ... + 1 if str is not a palindrome return memo[str] 

Basically, you delete each character in turn and save the answer for the resulting string. The more identical characters in a string, the faster it will be.

I'm not sure how to do this more efficiently, I will update it if I find out.

Answer 4

For a string with N elements, there are 2 ^ N possible substrings (including the entire string and the empty substring). Thus, we can encode each substring with a number with "1" bit in the bit position for each omitted (or existing) character and bit "0" otherwise. (assuming the string length is less than the number of bits in int (size_t here), otherwise you will need a different representation for the bit string):

 #include <stdio.h> #include <string.h> char string[] = "AbbA"; int is_palindrome (char *str, size_t len, size_t mask); int main(void) { size_t len,mask, count; len = strlen(string); count =0; for (mask = 1; mask < (1ul <<len) -1; mask++) { if ( is_palindrome (string, len, mask)) continue; count++; } fprintf(stderr, "Len:=%u, Count=%u \n" , (unsigned) len , (unsigned) count ); return 0; } int is_palindrome (char *str, size_t len, size_t mask) { size_t l,r,pop; for (pop=l=0, r = len -1; l < r; ) { if ( mask & (1u <<l)) { l++; continue; } if ( mask & (1u <<r)) { r--; continue; } if ( str[l] == str[r] ) return 1; l++,r--; pop++; } return (pop <1) ? 1: 0; } 

Answer 5

Here is the version of Haskell:

 import Data.List listNonPalindromes string = filter (isNotPalindrome) (subsequences string) where isNotPalindrome str | fst substr == snd substr = False | otherwise = True where substr = let a = splitAt (div (length str) 2) str in (reverse (fst a), if even (length str) then snd a else drop 1 (snd a)) howManyNonPalindromes string = length $ listNonPalindromes string 

* Home> listNonPalindromes "b99b"
["b9", "b9", "b99", "9b", "9b", "99b"]
* Home> howManyNonPalindromes "b99b"
6