神刀安全网

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

Given a binary string, count minimum number ofsubsequences to be removed to make it an empty string.

Examples:

Input: str[] = "10001" Output: 1 Since the whole string is palindrome,  we need only one removal.  Input: str[] = "10001001" Output: 2 We can remove the middle 1 as first  removal, after first removal string becomes 1000001 which is a palindrome.

Expected time complexity : O(n)

We strongly recommend you to minimize your browser and try this yourself first.

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. Why? 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.

// C++ program to count minimum palindromic subsequences // to be removed to make an string empty. #include <bits/stdc++.h> using namespace std;  // A function to check if a string str is 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; }  // Driver code to test above int main() {    cout << minRemovals("010010") << endl;    cout << minRemovals("0100101") << endl;    return 0; }

Output :

Exercises:

  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

This problem and solution are contributed by Hardik Gulati . Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Minimum number of palindromic subsequences to be removed to empty a binary string

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址