Número mínimo de subsecuencias palindrómicas que se eliminarán para vaciar una string binaria

Dada una string binaria, cuente el número mínimo de subsecuencias que se eliminarán para convertirla en una string vacía.

Ejemplos: 

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.

Complejidad de tiempo esperada : O(n)

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

El problema es simple y se puede resolver fácilmente usando los siguientes dos hechos. 

1. Si la string dada es palíndromo, solo necesitamos una eliminación. 
2. De lo contrario, necesitamos dos eliminaciones. Tenga en cuenta que cada string binaria tiene todos los 1 como una subsecuencia y todos los 0 como otra subsecuencia. Podemos eliminar cualquiera de las dos subsecuencias para obtener una string unaria. Una string unaria es siempre palíndromo. 

Implementación:

// 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] == '\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 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.

# 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# 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 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"), "\n";
echo minRemovals("0100101") , "\n";
 
// This code is contributed by ajit
?>

<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

Ejercicios: 

1. Extienda la solución anterior para contar el número mínimo de subsecuencias que se eliminarán para convertirlo en una string vacía.
2. ¿Cuál es el número máximo de strings ternarias?

Este problema y solución son aportados por Hardik Gulati . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.