Given a string str, the task is to remove all the consecutive duplicates from the string str and check if the final string is palindrome or not. Print “Yes” if it is a palindromic else print “No”.
Examples:
Input: str = “abbcbbbaaa”
Output: Yes
Explanation:
On removing all consecutive duplicates characters, the string becomes “abcba” which is a palindrome.Input: str = “aaabbbaaccc”
Output: No
Explanation:
On removing all consecutive duplicates characters, the string becomes “abac” which is not a palindrome.
Approach: The idea is to create a new string from the given string and check if the new string is palindromic or not. Below are the steps:
- Initialise the new string newStr = “”.
- Iterate through all the characters of the given string one by one and if the current character is the different from the previous character, then append this character to the new string newStr.
- Else check for the next character.
- Check if the final string formed is palindrome or not. Print “Yes” if it is a palindromic else print “No”.
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 string // is palindrome or not bool isPalindrome(string str) { // Length of the string int len = str.length(); // Check if its a palindrome for ( int i = 0; i < len; i++) { // If the palindromic // condition is not met if (str[i] != str[len - i - 1]) return false ; } // Return true as str is palindromic return true ; } // Function to check if string str is // palindromic after removing every // consecutive characters from the str bool isCompressablePalindrome(string str) { // Length of the string str int len = str.length(); // Create an empty // compressed string string compressed = "" ; // The first character will // always be included in // the final string compressed.push_back(str[0]); // Check all the characters // of the string for ( int i = 1; i < len; i++) { // If the current character // is not same as its previous // one, then insert it in the // final string if (str[i] != str[i - 1]) compressed.push_back(str[i]); } // Check if the compressed // string is a palindrome return isPalindrome(compressed); } // Driver Code int main() { // Given string string str = "abbcbbbaaa" ; // Function call if (isCompressablePalindrome(str)) cout << "Yes\n" ; else cout << "No\n" ; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if a String // is palindrome or not static boolean isPalindrome(String str) { // Length of the String int len = str.length(); // Check if its a palindrome for ( int i = 0 ; i < len; i++) { // If the palindromic // condition is not met if (str.charAt(i) != str.charAt(len - i - 1 )) return false ; } // Return true as str is palindromic return true ; } // Function to check if String str is // palindromic after removing every // consecutive characters from the str static boolean isCompressablePalindrome(String str) { // Length of the String str int len = str.length(); // Create an empty // compressed String String compressed = "" ; // The first character will // always be included in // the final String compressed = String.valueOf(str.charAt( 0 )); // Check all the characters // of the String for ( int i = 1 ; i < len; i++) { // If the current character // is not same as its previous // one, then insert it in the // final String if (str.charAt(i) != str.charAt(i - 1 )) compressed += str.charAt(i); } // Check if the compressed // String is a palindrome return isPalindrome(compressed); } // Driver Code public static void main(String[] args) { // Given String String str = "abbcbbbaaa" ; // Function call if (isCompressablePalindrome(str)) System.out.print( "Yes\n" ); else System.out.print( "No\n" ); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approach # Function to check if a string # is palindrome or not def isPalindrome( Str ): # Length of the string Len = len ( Str ) # Check if its a palindrome for i in range ( Len ): # If the palindromic # condition is not met if ( Str [i] ! = Str [ Len - i - 1 ]): return False # Return true as Str is palindromic return True # Function to check if string str is # palindromic after removing every # consecutive characters from the str def isCompressablePalindrome( Str ): # Length of the string str Len = len ( Str ) # Create an empty compressed string compressed = "" # The first character will always # be included in final string compressed + = Str [ 0 ] # Check all the characters # of the string for i in range ( 1 , Len ): # If the current character # is not same as its previous # one, then insert it in # the final string if ( Str [i] ! = Str [i - 1 ]): compressed + = Str [i] # Check if the compressed # string is a palindrome return isPalindrome(compressed) # Driver Code if __name__ = = '__main__' : # Given string Str = "abbcbbbaaa" # Function call if (isCompressablePalindrome( Str )): print ( "Yes" ) else : print ( "No" ) # This code is contributed by himanshu77 |
C#
// C# program for the above approach using System; class GFG{ // Function to check if a String // is palindrome or not static bool isPalindrome(String str) { // Length of the String int len = str.Length; // Check if its a palindrome for ( int i = 0; i < len; i++) { // If the palindromic // condition is not met if (str[i] != str[len - i - 1]) return false ; } // Return true as str is palindromic return true ; } // Function to check if String str is // palindromic after removing every // consecutive characters from the str static bool isCompressablePalindrome(String str) { // Length of the String str int len = str.Length; // Create an empty // compressed String String compressed = "" ; // The first character will // always be included in // the readonly String compressed = String.Join( "" , str[0]); // Check all the characters // of the String for ( int i = 1; i < len; i++) { // If the current character // is not same as its previous // one, then insert it in the // readonly String if (str[i] != str[i - 1]) compressed += str[i]; } // Check if the compressed // String is a palindrome return isPalindrome(compressed); } // Driver Code public static void Main(String[] args) { // Given String String str = "abbcbbbaaa" ; // Function call if (isCompressablePalindrome(str)) Console.Write( "Yes\n" ); else Console.Write( "No\n" ); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program for the above approach // Function to check if a String // is palindrome or not function isPalindrome(str) { // Length of the String let len = str.length; // Check if its a palindrome for (let i = 0; i < len; i++) { // If the palindromic // condition is not met if (str[i] != str[len - i - 1]) return false ; } // Return true as str is palindromic return true ; } // Function to check if String str is // palindromic after removing every // consecutive characters from the str function isCompressablePalindrome(str) { // Length of the String str let len = str.length; // Create an empty // compressed String let compressed = "" ; // The first character will // always be included in // the readonly String compressed = str[0]; // Check all the characters // of the String for (let i = 1; i < len; i++) { // If the current character // is not same as its previous // one, then insert it in the // readonly String if (str[i] != str[i - 1]) compressed += str[i]; } // Check if the compressed // String is a palindrome return isPalindrome(compressed); } // Given String let str = "abbcbbbaaa" ; // Function call if (isCompressablePalindrome(str)) document.write( "Yes" + "</br>" ); else document.write( "No" ); // This code is contributed by divyeshrabadiya07. </script> |
Yes
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N) as extra space is required for string compressed.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!