## Sunday, May 8, 2016

### Minimum number of palindromic subsequences to be removed to empty a binary string - GeeksforGeeks

Minimum number of palindromic subsequences to be removed to empty a binary string - GeeksforGeeks
Given a binary string, count minimum number of subsequences to be removed to make it an empty string.
```Input: str[] = "10001001"
Output: 2
We can remove the middle 1 as first
removal, after first removal string
becomes 1000001 which is a palindrome.```
The problem is simple and can be solved easily using below two facts.
1) If given string is palindrome, we need only one removal.
2) Else we need two removals. Note that every binary string has all 1’s as a subsequence and all 0’s as another subsequence. We can remove any of the two subsequences to get a unary string. A unary string is always palindrome.

`bool` `isPalindrome(``const` `char` `*str)`
`{`
`    ``// Start from leftmost and rightmost corners of str`
`    ``int` `l = 0;`
`    ``int` `h = ``strlen``(str) - 1;`

`    ``// Keep comparing characters while they are same`
`    ``while` `(h > l)`
`        ``if` `(str[l++] != str[h--])`
`            ``return` `false``;`

`    ``return` `true``;`
`}`

`// Returns count of minimum palindromic subseuqnces to`
`// be removed to make string empty`
`int` `minRemovals(``const` `char` `*str)`
`{`
`   ``// If string is empty`
`   ``if` `(str[0] == ``'\0'``)`
`      ``return` `0;`

`   ``// If string is palindrome`
`   ``if` `(isPalindrome(str))`
`      ``return` `1;`

`   ``// If string is not palindrome`
`   ``return` `2;`
`}`

1. Extend the above solution to count minimum number of subsequences to be removed to make it an empty string.
2. What is the maximum count for ternary strings
Read full article from Minimum number of palindromic subsequences to be removed to empty a binary string - GeeksforGeeks