Rearrange characters of a string to make it a concatenation of palindromic substrings

Rearrange characters of a string to make it a concatenation of palindromic substrings

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++

#include <bits/stdc++.h> using namespace std;    void canSplit(string& S) {          vector<int> frequency(26, 0);        int cnt_singles = 0;        int k = 0;             for (int i = 0; i < S.length(); i++)                              frequency[S[i] - 'a']++;        int odd = 0, eve = 0;             for (int i = 0; i < 26; i++) {                     if (frequency[i]) {             odd += (frequency[i] & 1);             eve += frequency[i] / 2;         }     }             if (eve >= odd)         cout << "Yes";     else         cout << "No"; }    int main() {     string S = "aaabbbccc";     canSplit(S);        return 0; }

Output:

Yes

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)