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 the characters are not the same
- 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:
No
Time Complexity: O(N), Where N is the length of the string.
Space Complexity: O(1)