Рубрики

Минимальное количество палиндромных подпоследовательностей, которые нужно удалить, чтобы очистить двоичную строку

Для данной двоичной строки подсчитайте минимальное количество подпоследовательностей, которые нужно удалить, чтобы сделать ее пустой строкой.

Примеры :

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 ++ программа для подсчета минимальных палиндромных подпоследовательностей
// для удаления пустой строки.
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки, является ли строка str палиндромом

bool isPalindrome(const char *str)

{

    // Начинаем с самого левого и правого углов str

    int l = 0;

    int h = strlen(str) - 1;

  

    // Продолжаем сравнивать символы, пока они одинаковые

    while (h > l)

        if (str[l++] != str[h--])

            return false;

  

    return true;

}

  
// Возвращает количество минимальных палиндромных побочных эффектов в
// удаляем, чтобы сделать строку пустой

int minRemovals(const char *str)

{

   // Если строка пуста

   if (str[0] == '')

      return 0;

  

   // Если строка палиндром

   if (isPalindrome(str))

      return 1;

  

   // Если строка не является палиндромом

   return 2;

}

  
// Код драйвера для проверки выше

int main()

{

   cout << minRemovals("010010") << endl;

   cout << minRemovals("0100101") << endl;

   return 0;

}

Джава

// Java-программа для подсчета минимального палиндрома
// подпоследовательности, которые нужно удалить, чтобы сделать
// пустая строка

import java.io.*;

  

class GFG {

      
// Функция для проверки, если строка
// палиндром

static boolean isPalindrome(String str)

{

    // Начинаем слева и справа

    // углы ул

    int l = 0;

    int h = str.length() - 1;

  

    // Продолжаем сравнивать символы

    // пока они одинаковые

    while (h > l)

        if (str.charAt(l++) != str.charAt(h--))

            return false;

  

    return true;

}

  
// Возвращает количество минимальных палиндромных
// подразделы, которые будут удалены
// сделать строку пустой

static int minRemovals(String str)

{

    // Если строка пуста

    if (str.charAt(0) == '')

        return 0;

  

    // Если строка палиндром

    if (isPalindrome(str))

        return 1;

  

    // Если строка не является палиндромом

    return 2;

}

  
// Код драйвера для проверки выше

public static void main (String[] args) 

{

    System.out.println (minRemovals("010010"));

    System.out.println (minRemovals("0100101"));

          
}
}

  
// Этот код предоставлен vt_m.

python3

# Python программа для подсчета минимум
# палиндромные подпоследовательности к
# быть удаленным, чтобы сделать строку
# пусто

  
# Функция для проверки, если
# строка str является палиндромом

def isPalindrome(str):

      

    # Начинаем слева и

    # правые углы ул

    l = 0

    h = len(str) - 1

      

    # Продолжайте сравнивать персонажей

    # пока они одинаковые

    while (h > l):

        if (str[l] != str[h]):

            return 0

        l = l + 1

        h = h - 1

          

    return 1

      
# Возвращает количество минимумов
# палиндромные последующие
# быть удаленным, чтобы сделать строку
# пусто

def minRemovals(str):

      

    # Если строка пуста

    if (str[0] == ''):

        return 0

      

    # Если строка является палиндромом

    if (isPalindrome(str)):

        return 1

      

    # Если строка не является палиндромом

    return 2

      
# Код драйвера

print(minRemovals("010010"))

print(minRemovals("0100101"))

  
# Этот код предоставлен Sam007.

C #

// C # программа для подсчета минимального палиндрома
// подпоследовательности, которые нужно удалить, чтобы сделать
// пустая строка

using System;

  

class GFG

{

      

    // Функция для проверки, если

    // строка str является палиндромом

    static bool isPalindrome(String str)

    {

        // Начнем с самого левого и

        // самые правые углы ул

        int l = 0;

        int h = str.Length - 1;

      

        // Продолжаем сравнивать символы

        // пока они одинаковые

        while (h > l)

            if (str[l++] != str[h--])

                return false;

      

        return true;

    }

      

    // Возвращает количество минимальных палиндромных

    // подразделы, которые будут удалены

    // сделать строку пустой

    static int minRemovals(String str)

    {

        // Если строка пуста

        if (str[0] == '')

            return 0;

      

        // Если строка палиндром

        if (isPalindrome(str))

            return 1;

      

        // Если строка не является палиндромом

        return 2;

    }

      

    // Код драйвера для

    public static void Main () 

    {

        Console.WriteLine(minRemovals("010010"));

        Console.WriteLine(minRemovals("0100101"));

              

    }

      
}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для подсчета минимума
// палиндромные подпоследовательности к
// удаляем, чтобы сделать строку пустой.

  
// Функция для проверки, если
// строка str является палиндромом

function isPalindrome($str)

{

    // Начнем с самого левого и

    // самые правые углы ул

    $l = 0;

    $h = strlen($str) - 1;

  

    // Продолжаем сравнивать символы

    // пока они одинаковые

    while ($h > $l)

        if ($str[$l++] != $str[$h--])

            return false;

  

    return true;

}

  
// Возвращает количество минимумов
// палиндромные подпоследовательности
// для удаления
// строка пуста

function minRemovals($str)

{
// Если строка пуста

if ($str[0] == '')

    return 0;

  
// Если строка палиндром

if (isPalindrome($str))

    return 1;

  
// Если строка не является палиндромом

return 2;

}

  
// Код драйвера

echo minRemovals("010010"), "\n";

echo minRemovals("0100101") , "\n";

  
// Этот код предоставлен ajit
?>

Выход :

1
2

Упражнения:

  1. Расширьте приведенное выше решение, чтобы подсчитать минимальное количество подпоследовательностей, которые нужно удалить, чтобы сделать его пустой строкой.
  2. Каков максимальный счет для троичных струн

Эта проблема и решение внесены Hardik Gulati . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Минимальное количество палиндромных подпоследовательностей, которые нужно удалить, чтобы очистить двоичную строку

0.00 (0%) 0 votes