给定一个二进制字符串，计算 子序列 将其删除，使其成为空字符串。 例如：
null
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.
预期时间复杂度：O（n）
我们强烈建议您在继续解决方案之前单击此处并进行练习。
这个问题很简单，使用以下两个事实就可以很容易地解决。 1） 如果给定的字符串是回文的，我们只需要删除一次。 2） 否则我们需要两次移除。请注意，每个二进制字符串都有所有1作为子序列，所有0作为另一个子序列。我们可以去掉这两个子序列中的任何一个子序列，得到一元字符串。一元字符串总是回文的。
C++
// 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 subsequences to // be removed to make string empty int minRemovals( const char *str) { // If string is empty if (str[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; } |
JAVA
// Java program to count minimum palindromic // subsequences to be removed to make // an string empty. import java.io.*; class GFG { // A function to check if a string // str is palindrome static boolean isPalindrome(String str) { // Start from leftmost and rightmost // corners of str int l = 0 ; int h = str.length() - 1 ; // Keep comparing characters // while they are same while (h > l) if (str.charAt(l++) != str.charAt(h--)) return false ; return true ; } // Returns count of minimum palindromic // subsequences to be removed to // make string empty static int minRemovals(String str) { // If string is empty if (str.charAt( 0 ) == '' ) return 0 ; // If string is palindrome if (isPalindrome(str)) return 1 ; // If string is not palindrome return 2 ; } // Driver code to test above public static void main (String[] args) { System.out.println (minRemovals( "010010" )); System.out.println (minRemovals( "0100101" )); } } // This code is contributed by vt_m. |
Python3
# Python program to count minimum # palindromic subsequences to # be removed to make an string # empty. # A function to check if a # string str is palindrome def isPalindrome( str ): # Start from leftmost and # rightmost corners of str l = 0 h = len ( str ) - 1 # Keep comparing characters # while they are same while (h > l): if ( str [l] ! = str [h]): return 0 l = l + 1 h = h - 1 return 1 # Returns count of minimum # palindromic subsequences to # be removed to make string # empty def minRemovals( str ): #If string is empty if ( str [ 0 ] = = ''): return 0 #If string is palindrome if (isPalindrome( str )): return 1 # If string is not palindrome return 2 # Driver code print (minRemovals( "010010" )) print (minRemovals( "0100101" )) # This code is contributed by Sam007. |
C#
// C# program to count minimum palindromic // subsequences to be removed to make // an string empty. using System; class GFG { // A function to check if a // string str is palindrome static bool isPalindrome(String str) { // Start from leftmost and // rightmost corners of str int l = 0; int h = str.Length - 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 // subsequences to be removed to // make string empty static int minRemovals(String str) { // If string is empty if (str[0] == '' ) return 0; // If string is palindrome if (isPalindrome(str)) return 1; // If string is not palindrome return 2; } // Driver code to public static void Main () { Console.WriteLine(minRemovals( "010010" )); Console.WriteLine(minRemovals( "0100101" )); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to count minimum // palindromic subsequences to // be removed to make an string empty. // A function to check if a // string str is palindrome function isPalindrome( $str ) { // Start from leftmost and // rightmost corners of str $l = 0; $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 subsequences // to be removed to make // string empty function minRemovals( $str ) { // If string is empty if ( $str [0] == '' ) return 0; // If string is palindrome if (isPalindrome( $str )) return 1; // If string is not palindrome return 2; } // Driver Code echo minRemovals( "010010" ), "" ; echo minRemovals( "0100101" ) , "" ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to count // minimum palindromic // subsequences to be removed to make // an string empty. // A function to check if a // string str is palindrome function isPalindrome(str) { // Start from leftmost and // rightmost corners of str let l = 0; let h = str.length - 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 // subsequences to be removed to // make string empty function minRemovals(str) { // If string is empty if (str[0] == '' ) return 0; // If string is palindrome if (isPalindrome(str)) return 1; // If string is not palindrome return 2; } // Driver Code document.write(minRemovals( "010010" ) + "</br>" ); document.write(minRemovals( "0100101" )); </script> |
输出：
1 2
练习：
- 扩展上述解决方案，计算要删除的子序列的最小数量，使其成为空字符串。
- 三元字符串的最大计数是多少
这个问题和解决方案是由 哈迪克·古拉蒂 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
