Minimum number of palindromic subsequences to be removed to empty a binary string
Last Updated :
20 Feb, 2023
Given a binary string, count minimum number of subsequences 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)
The problem is simple and can be solved easily using below two facts.
- If given string is palindrome, we need only one removal.
- 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.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(const char *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] == '\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"));
}
}
|
Python3
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"))
|
C#
using System;
class GFG
{
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"));
}
}
|
PHP
<?php
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";
?>
|
Javascript
<script>
function isPalindrome(str)
{
let l = 0;
let h = str.length - 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;
}
document.write(minRemovals("010010") + "</br>");
document.write(minRemovals("0100101"));
</script>
|
Time Complexity: O(n)
Auxiliary Space : O(1)
Exercises:
- Extend the above solution to count minimum number of subsequences to be removed to make it an empty string.
- What is the maximum count for ternary strings
This problem and solution are contributed by Hardik Gulati.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...