Check if given string can be made Palindrome by removing only single type of character
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
Approach: The task can be solved by iterating over each unique character in the given string, and removing its occurrences wherever there is a mismatch, if a valid palindrome is found, after removing occurrences of the same character any number of times, return “Yes” else return “No“.
Follow the below steps to solve the problem:
- Start iterating over each unique character of the string, whose occurrences are to be deleted
- Use the two-pointer technique, to check for a mismatch, Place l at the start of the string and r at the end of the string
- If S[l] == S[r], increment l, and decrement r.
- If S[l]!= S[r], check if S[l[ == char, do l++, else if S[r] == char, do r–
- If none of the conditions hold means the given can’t be converted into a palindrome
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a palindrome is // possible or not string isPossible(string S) { // Stores the length of string int n = ( int )S.length(); // Stores the unique characters in // the string set< char > st; for ( int i = 0; i < n; i++) { st.insert(S[i]); } // Check if valid palindrome is // possible or not bool check = false ; // Iterating over unique characters // of the string for ( auto ele : st) { // Pointers to check the condition int low = 0, high = n - 1; bool flag = true ; // Iterating over the string for ( int i = 0; i < n; i++) { if (S[low] == S[high]) { // Updating low and high low++; high--; } else { if (S[low] == ele) { // Updating low low++; } else if (S[high] == ele) { // Updating high high--; } else { // It is impossible // to make palindrome // by removing // occurrences of char flag = false ; break ; } } } // If palindrome is formed // break the loop if (flag == true ) { check = true ; break ; } } if (check) return "Yes" ; else return "No" ; } // Driver Code int main() { string S = "abczdzacb" ; cout << isPossible(S); return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { // Function to check if a palindrome is // possible or not static String isPossible(String S) { // Stores the length of string int n = S.length(); // Stores the unique characters in // the string Set<Character> st = new HashSet<Character>(); for ( int i = 0 ; i < n; i++) { st.add(S.charAt(i)); } // Check if valid palindrome is // possible or not boolean check = false ; // Iterating over unique characters // of the string for (Character ele : st) { // Pointers to check the condition int low = 0 , high = n - 1 ; boolean flag = true ; // Iterating over the string for ( int i = 0 ; i < n; i++) { if (S.charAt(low) == S.charAt(high)) { // Updating low and high low++; high--; } else { if (S.charAt(low) == ele) { // Updating low low++; } else if (S.charAt(high)== ele) { // Updating high high--; } else { // It is impossible // to make palindrome // by removing // occurrences of char flag = false ; break ; } } } // If palindrome is formed // break the loop if (flag == true ) { check = true ; break ; } } if (check) return "Yes" ; else return "No" ; } // Driver Code public static void main (String[] args) { String S = "abczdzacb" ; System.out.println(isPossible(S)); } } // This code is contributed by Potta Lokesh |
Python3
# python program for the above approach # Function to check if a palindrome is # possible or not def isPossible(S): # Stores the length of string n = len (S) # Stores the unique characters in # the string st = set () for i in range ( 0 , n): st.add(S[i]) # Check if valid palindrome is # possible or not check = False # Iterating over unique characters # of the string for ele in st: # Pointers to check the condition low = 0 high = n - 1 flag = True # Iterating over the string for i in range ( 0 , n): if (S[low] = = S[high]): # Updating low and high low + = 1 high - = 1 else : if (S[low] = = ele): # Updating low low + = 1 elif (S[high] = = ele): # Updating high high - = 1 else : # It is impossible # to make palindrome # by removing # occurrences of char flag = False break # If palindrome is formed # break the loop if (flag = = True ): check = True break if (check): return "Yes" else : return "No" # Driver Code if __name__ = = "__main__" : S = "abczdzacb" print (isPossible(S)) # This code is contributed by rakeshsahni |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Function to check if a palindrome is // possible or not static String isPossible(String S) { // Stores the length of string int n = S.Length; // Stores the unique characters in // the string HashSet< char > st = new HashSet< char >(); for ( int i = 0; i < n; i++) { st.Add(S[i]); } // Check if valid palindrome is // possible or not bool check = false ; // Iterating over unique characters // of the string foreach ( char ele in st) { // Pointers to check the condition int low = 0, high = n - 1; bool flag = true ; // Iterating over the string for ( int i = 0; i < n; i++) { if (S[low] == S[high]) { // Updating low and high low++; high--; } else { if (S[low] == ele) { // Updating low low++; } else if (S[high]== ele) { // Updating high high--; } else { // It is impossible // to make palindrome // by removing // occurrences of char flag = false ; break ; } } } // If palindrome is formed // break the loop if (flag == true ) { check = true ; break ; } } if (check) return "Yes" ; else return "No" ; } // Driver Code public static void Main(String[] args) { String S = "abczdzacb" ; Console.WriteLine(isPossible(S)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach // Function to check if a palindrome is // possible or not function isPossible(S) { // Stores the length of string let n = S.length; // Stores the unique characters in // the string let st = new Set(); for (let i = 0; i < n; i++) { st.add(S[i]); } // Check if valid palindrome is // possible or not let check = false ; // Iterating over unique characters // of the string for (ele of st) { // Pointers to check the condition let low = 0, high = n - 1; let flag = true ; // Iterating over the string for (let i = 0; i < n; i++) { if (S[low] == S[high]) { // Updating low and high low++; high--; } else { if (S[low] == ele) { // Updating low low++; } else if (S[high] == ele) { // Updating high high--; } else { // It is impossible // to make palindrome // by removing // occurrences of char flag = false ; break ; } } } // If palindrome is formed // break the loop if (flag == true ) { check = true ; break ; } } if (check) return "Yes" ; else return "No" ; } // Driver Code let S = "abczdzacb" ; document.write(isPossible(S)); // This code is contributed by saurabh_jaiswal. </script> |
Yes
Time Complexity: O(n*26)
Auxiliary Space: O(1) because the size of set cannot exceed 26 if only lowercase alphabets are considered.