Check If The Given String Can Be Made Palindrome By Removing The Only A Single Type Of Character

Check If The Given String Can Be Made Palindrome By Removing The Only A Single Type Of Character Let’s see below example.

The aim is to determine whether a string S can be rendered palindrome by eliminating any number of repetitions of the same character.

Examples:

Input: S = “abczdzacb“
Output: Yes
Explanation: Remove first and second occurrence of character ‘a’. 
String S becomes “bczdzcb”, which is a palindrome.

Input: S = “madem”
Output: No
Explanation: Since only we can remove 1 character of any frequency only once. 
There is no such character removing which a palindrome can be made.

Approach:

The palindrome property can be used to overcome this problem. It is self-evident that deleting repetitions of the same character from the full does not change the palindromic quality of the text. As a result, all instances of that character can be erased. Check the string from both ends if they are different, then check the string after removing all occurrences of the character from both ends. The answer is Yes if any of the removals satisfy the palindromic requirement; otherwise, the answer is No.

Follow the steps below to solve the problem:

Iterate using a loop in the range of (0, N/2)
Now check if characters from both the ends are equal or not
- If the characters are not the same
  - Check if it is Palindrome after removing the entire occurrence of character from both ends.
  - If removing entire occurrences of a character from any end is a palindrome print “YES” and stop iteration.
If after the whole traversal, no such palindrome found print “NO”.

Below is the implementation of the above approach:

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to check whether the string
// is palindrome after removal or
// neglecting character c
bool check_palindrome(string str, char c)
{
	int n = str.length(), i = 0, j = n - 1;

	while (i < j) {

		// If it is same as c neglect
		// this and move front
		if (str[i] == c)
			i++;

		// If it is same as c neglect
		// this and move back
		else if (str[j] == c)
			j--;

		// If they are not same it is
		// not a palindrome so return 0
		else if (str[i] != str[j])
			return 0;

		// It can be a palindrome so move
		// and check for remaining string
		else
			i++, j--;
	}

	return 1;
}

// Function to check if it is possible to
// form a palindrome after removal of
// any number of same characters once
string make_palindrome(string str)
{
	bool is_palindrome = 1;
	int n = str.length();

	// If n==1 || n==2 it is always possible
	if (n == 1 || n == 2) {
		return "YES";
	}

	// Check the character from both the ends
	// of the string
	for (int i = 0; i < n / 2; ++i) {

		// If the characters are not equal
		if (str[i] != str[n - 1 - i]) {

			// Remove str[i] and check if
			// it is a palindrome or
			// Remove str[n-i-1] and check
			// if it is a palindrome
			is_palindrome
				= check_palindrome(str, str[i])
				|| check_palindrome(
						str, str[n - 1 - i]);
			break;
		}
	}
	if (is_palindrome)
		return "Yes";

	else
		return "No";
}

// Driver Code
int main()
{
	string S = "madem";

	string res = make_palindrome(S);
	cout << (res);
	return 0;
}

Output: