Given a string S, the task is to whether a string can be made palindrome after removing the occurrences of the same character, any number of times
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: This problem can be solved by using the property of palindrome. It is obvious that removing the occurrences of the same character from the entire does not affect the palindromic nature. So the entire occurrences of that character can also be removed. So check the string from both the ends if they are not the same then check the string after the removal of entire occurrences of the character at both the ends. If any of the removals satisfies the palindromic condition then the answer is Yes else 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++
// 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 cbool 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 oncestring 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 Codeint main(){ string S = "madem"; string res = make_palindrome(S); cout << (res); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Function to check whether the string// is palindrome after removal or// neglecting character cstatic boolean 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.charAt(i) == c) i++; // If it is same as c neglect // this and move back else if (str.charAt(j) == c) j--; // If they are not same it is // not a palindrome so return 0 else if (str.charAt(i) != str.charAt(j)) return false; // It can be a palindrome so move // and check for remaining string else { i++; j--; } } return true;}// Function to check if it is possible to// form a palindrome after removal of// any number of same characters oncestatic String make_palindrome(String str){ boolean is_palindrome = true; 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.charAt(i) != str.charAt(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.charAt(i)) || check_palindrome( str, str.charAt(n - 1 - i)); break; } } if (is_palindrome) return "Yes"; else return "No";}// Driver Codepublic static void main(String args[]){ String S = "madem"; String res = make_palindrome(S); System.out.println(res);}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach# Function to check whether the string# is palindrome after removal or# neglecting character cdef check_palindrome (str, c): n = len(str) i = 0 j = n - 1 while (i < j): # If it is same as c neglect # this and move front if (str[i] == c): i += 1 # If it is same as c neglect # this and move back elif (str[j] == c): j -= 1 # If they are not same it is # not a palindrome so return 0 elif (str[i] != str[j]): return 0 # It can be a palindrome so move # and check for remaining string else: i += 1 j -= 1 return 1# Function to check if it is possible to# form a palindrome after removal of# any number of same characters oncedef make_palindrome (str): is_palindrome = 1 n = len(str) # If n==1 || n==2 it is always possible if (n == 1 or n == 2): return "YES" # Check the character from both the ends # of the string for i in range(n // 2): # 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]) or check_palindrome(str, str[n - 1 - i]) break if (is_palindrome): return "Yes" else: return "No"# Driver CodeS = "madem"res = make_palindrome(S)print(res)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ // Function to check whether the string// is palindrome after removal or// neglecting character cstatic 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 false; // It can be a palindrome so move // and check for remaining string else { i++; j--; } } return true;}// Function to check if it is possible to// form a palindrome after removal of// any number of same characters oncestatic string make_palindrome(string str){ bool is_palindrome = true; 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 Codepublic static void Main(){ string S = "madem"; string res = make_palindrome(S); Console.Write(res);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to check whether the string // is palindrome after removal or // neglecting character c const check_palindrome = (str, c) => { let 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 const make_palindrome = (str) => { let is_palindrome = 1; let 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 (let i = 0; i < parseInt(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 let S = "madem"; let res = make_palindrome(S); document.write(res);// This code is contributed by rakeshsahni</script> |
Output
No
Time Complexity: O(N), Where N is the length of the string.
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
