Given a string S consisting of lowercase alphabets, the task is to check whether the given string can be rearranged such that the string can be split into non-overlapping palindromic substrings of at least length 2. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: S = “aaaabbcdd”
Output: Yes
Explanation: Rearrange the given string S to “acaaabbdd”, which can be split into non-overlapping palindromic substrings “aca”, “aa”, “bb”, “dd”.Input: S = “ccddgggggefs”
Output: No
Approach: The given problem can be solved by rearranging the characters of the string into substrings of length 2, consisting of single distinct character. If there exists any character with odd frequency, then it place them in the middle of the palindromic substrings of length 2.
Follow the steps below to solve the problem:
- Initialize an auxiliary array, say frequency[] of size 26, to store the frequency of every character present in the string S.
- Traverse the given string S and update the frequency of each character in the array frequency[].
- Initialize two variables, say odd and even both as 0, to store the frequency of odd elements and the number of palindromic substrings of length 2 formed.
- Traverse the array frequency[] and if the value of frequency[i] is greater than 0, then add the value (frequency[i] & 1) and (frequency[i] / 2) to the variable odd and even respectively.
- After completing the above steps, if the value of odd is at most even, then print “Yes”. Otherwise, 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 can be // modified such that it can be split into // palindromic substrings of length >= 2 void canSplit(string& S) { // Stores frequencies of characters vector< int > frequency(26, 0); int cnt_singles = 0; int k = 0; // Traverse the string for ( int i = 0; i < S.length(); i++) // Update frequency // of each character frequency[S[i] - 'a' ]++; int odd = 0, eve = 0; // Traverse the frequency array for ( int i = 0; i < 26; i++) { // Update values of odd and eve if (frequency[i]) { odd += (frequency[i] & 1); eve += frequency[i] / 2; } } // Print the result if (eve >= odd) cout << "Yes" ; else cout << "No" ; } // Driver Code int main() { string S = "aaabbbccc" ; canSplit(S); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to check if a string can be // modified such that it can be split into // palindromic substrings of length >= 2 static void canSplit(String S) { // Stores frequencies of characters int frequency[] = new int [ 26 ]; int cnt_singles = 0 ; int k = 0 ; // Traverse the string for ( int i = 0 ; i < S.length(); i++) // Update frequency // of each character frequency[S.charAt(i) - 'a' ]++; int odd = 0 , eve = 0 ; // Traverse the frequency array for ( int i = 0 ; i < 26 ; i++) { // Update values of odd and eve if (frequency[i] != 0 ) { odd += (frequency[i] & 1 ); eve += frequency[i] / 2 ; } } // Print the result if (eve >= odd) System.out.println( "Yes" ); else System.out.println( "No" ); } // Driver Code public static void main(String[] args) { String S = "aaabbbccc" ; canSplit(S); } } |
Python3
# Python3 program for the above approach # Function to check if a string can be # modified such that it can be split into # palindromic substrings of length >= 2 def canSplit(S): # Stores frequencies of characters frequency = [ 0 ] * 26 cnt_singles = 0 k = 0 # Traverse the string for i in range ( len (S)): # Update frequency # of each character frequency[ ord (S[i]) - ord ( 'a' )] + = 1 odd = 0 eve = 0 # Traverse the frequency array for i in range ( 26 ): # Update values of odd and even if (frequency[i]): odd + = (frequency[i] & 1 ) eve + = frequency[i] / / 2 # Print the result if (eve > = odd): print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = "__main__" : S = "aaabbbccc" canSplit(S) # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; public class GFG { // Function to check if a string can be // modified such that it can be split into // palindromic substrings of length >= 2 static void canSplit( string S) { // Stores frequencies of characters int []frequency = new int [26]; int cnt_singles = 0; int k = 0; // Traverse the string for ( int i = 0; i < S.Length; i++) // Update frequency // of each character frequency[S[i] - 'a' ]++; int odd = 0, eve = 0; // Traverse the frequency array for ( int i = 0; i < 26; i++) { // Update values of odd and eve if (frequency[i] != 0) { odd += (frequency[i] & 1); eve += frequency[i] / 2; } } // Print the result if (eve >= odd) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } // Driver Code public static void Main( string [] args) { string S = "aaabbbccc" ; canSplit(S); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program for the above approach // Function to check if a string can be // modified such that it can be split into // palindromic substrings of length >= 2 function canSplit(S){ // Stores frequencies of characters let frequency = new Array(26).fill(0) let cnt_singles = 0 let k = 0 // Traverse the string for (let i = 0; i < S.length; i++){ // Update frequency // of each character frequency[S.charCodeAt(i) - 'a' .charCodeAt(0)] += 1 } let odd = 0 let eve = 0 // Traverse the frequency array for (let i = 0; i < 26; i++){ // Update values of odd and eve if (frequency[i]){ odd += (frequency[i] & 1) eve += frequency[i] // 2 } } // document.write the result if (eve >= odd){ document.write( "Yes" ) } else { document.write( "No" ) } } // Driver Code let S = "aaabbbccc" canSplit(S) // This code is contributed by gfgking </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!