Given a palindromic string, in how many ways we can convert it to a non palindrome by removing one more more characters from it? [closed]

Question

Given a palindromic string, in how many ways we can convert it to a non palindrome by removing one more more characters from it?

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

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

How to approach this one?

PS:Two ways are considered different if there exists an i such that character at index i is removed in one way and not removed in another.

Answer 1

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

This algorithm counts subsequences by the 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 palindromic subsequences, we build up the count based on intervals of the sequence. Specifically, we define:

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

Pi,j = the number of palindromic subsequences of Si,j

Now, every one-element interval is a palindrome, so:

Pi,i = 1 for all i < n

If a substring does not begin and end with the same element (i.e., Si ≠ Sj) then the palindromic subsequences consist of:

• Those which contain Si but do not contain Sj

• Those which contain Sj but do not contain Si

• Those which contain neither Si nor Sj

Now, note that Pi,j-1 includes both the first and the third set of subsequences, while Pi+1,j includes both the second and the third set; Pi+1,j-1 is precisely the third set. Consequently:

Pi,j = Pi+1,j + Pi,j-1 − Pi+1,j-1 if Si ≠ Sj

But what if Si = Sj? In that case, we have to add the palindromes consisting of Si followed by a subsequence palindrome from Si+1,j-1 followed by Sj, as well as the palindromic subsequence consisting of just the start and end characters. (Technically, an empty sequence is a palindrome, but we don't count those here.) The number of subsequences we add is P_i+1,j-1 + 1, which cancels out the subtracted double count in the above equation. So:

Pi,j = Pi+1,j + Pi,j-1 + 1 if Si = Sj.

In order to save space, we can actually compute Pi,i+k for 0 ≤ i < |S|-k for increasing values of k; we only need to retain two of these vectors in order to generate the final result P_0,|S|-1.

---

EDIT:

Here's a little python program; the first one computes the number of palindromic subsequences, as above, and the driver computes the number of non-palindromic subsequences (i.e. the number of ways to remove zero or more elements and produce a non-palindrome; if the original sequence is a palindrome, then it's 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 you can remove one or more characters and keep the string a palindrome. then subtract that from the total number of ways you can modify the string.

the most obvious way to modify a palindrome and keep it a palindrome is to remove the i'th and the (n-i)'th characters (n being the length of the string). there are 2^(n/2) ways you can do that.

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