Given a string S consisting of N lowercase alphabets, the task is to check if all the strings of at least length 2 formed by selecting every character of the string S only once are palindromic or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: S = “abbbaddzcz”
Output: Yes
Explanation: The palindromic strings of length greater than 1 are { “aa”, “bbb”, “dd”, “zcz”} and all the characters in the given string is used only once. Therefore, print “Yes”.Input: S = “abcd”
Output: No
Approach: The idea is to break the string into a palindromic strings of even length, and if there exists a character having frequency 1, then pair it with a palindromic string of even length. Follow the steps below to solve the problem:
- Initialize an array, say freq[], of size 26, to store the frequency of each character present in the string.
- Iterate over the characters of the given string S and update the frequency of each character in the array freq[].
- Initialize two variables, say O and E, to store the count of unique characters and characters having even frequencies respectively.
- Traverse the array freq[] and if freq[i] is equal to 1, then increment O by 1. Otherwise, increment E by 1.
- Check if E ? O, then print “Yes”. Otherwise, perform the following steps:
- Update O to O – E, to store the remaining unique characters after pairing.
- Traverse the array freq[] and if the value of O is at most 0, then break out of the loop. Otherwise, update O to O – (freq[i]/2) and then increment O by 1.
- After completing the above steps, if the value of O ? 0, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to check if a string can be// split into palindromic strings of at// least length 2 by including every// character exactly oncevoid checkPalindrome(string& s){ // Stores the frequency // of each character int a[26] = { 0 }; // Store the frequency of // characters with frequencies // 1 and even respectively int o = 0, e = 0; // Traverse the string s for (int i = 0; s[i] != '\0'; i++) a[(int)s[i] - 97]++; // Iterate over all the characters for (int i = 0; i < 26; i++) { // If the frequency is 1 if (a[i] == 1) o++; // If frequency is even else if (a[i] % 2 == 0 and a[i] != 0) e += (a[i] / 2); } // Print the result if (e >= o) cout << "Yes"; else { // Stores the number of characters // with frequency equal to 1 that // are not part of a palindromic string o = o - e; // Iterate over all the characters for (int i = 0; i < 26; i++) { // If o becomes less than 0, // then break out of the loop if (o <= 0) break; // If frequency of the current // character is > 2 and is odd if (o > 0 and a[i] % 2 == 1 and a[i] > 2) { int k = o; // Update the value of o o = o - a[i] / 2; // If a single character // is still remaining if (o > 0 or 2 * k + 1 == a[i]) { // Increment o by 1 o++; // Set a[i] to 1 a[i] = 1; } } } // Print the result if (o <= 0) cout << "Yes"; else cout << "No"; }}// Driver Codeint main(){ string S = "abbbaddzcz"; checkPalindrome(S); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to check if a string can be// split into palindromic strings of at// least length 2 by including every// character exactly oncestatic void checkPalindrome(String s){ // Stores the frequency // of each character int a[] = new int[26]; // Store the frequency of // characters with frequencies // 1 and even respectively int o = 0, e = 0; // Traverse the string s for(int i = 0; i < s.length(); i++) a[s.charAt(i) - 'a']++; // Iterate over all the characters for(int i = 0; i < 26; i++) { // If the frequency is 1 if (a[i] == 1) o++; // If frequency is even else if (a[i] % 2 == 0 && a[i] != 0) e += (a[i] / 2); } // Print the result if (e >= o) System.out.println("Yes"); else { // Stores the number of characters // with frequency equal to 1 that // are not part of a palindromic string o = o - e; // Iterate over all the characters for(int i = 0; i < 26; i++) { // If o becomes less than 0, // then break out of the loop if (o <= 0) break; // If frequency of the current // character is > 2 and is odd if (o > 0 && a[i] % 2 == 1 && a[i] > 2) { int k = o; // Update the value of o o = o - a[i] / 2; // If a single character // is still remaining if (o > 0 || 2 * k + 1 == a[i]) { // Increment o by 1 o++; // Set a[i] to 1 a[i] = 1; } } } // Print the result if (o <= 0) System.out.println("Yes"); else System.out.println("No"); }}// Driver Codepublic static void main(String[] args){ String S = "abbbaddzcz"; checkPalindrome(S);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to check if a string can be# split into palindromic strings of at# least length 2 by including every# character exactly oncedef checkPalindrome(s): # Stores the frequency # of each character a = [0] * 26 # Store the frequency of # characters with frequencies # 1 and even respectively o, e = 0, 0 # Traverse the string s for i in s: a[ord(i) - 97] += 1 # Iterate over all the characters for i in range(26): # If the frequency is 1 if (a[i] == 1): o += 1 # If frequency is even elif (a[i] % 2 == 0 and a[i] != 0): e += (a[i] // 2) # Print the result if (e >= o): print("Yes") else: # Stores the number of characters # with frequency equal to 1 that # are not part of a palindromic string o = o - e # Iterate over all the characters for i in range(26): # If o becomes less than 0, # then break out of the loop if (o <= 0): break # If frequency of the current # character is > 2 and is odd if (o > 0 and a[i] % 2 == 1 and a[i] > 2): k = o # Update the value of o o = o - a[i] // 2 # If a single character # is still remaining if (o > 0 or 2 * k + 1 == a[i]): # Increment o by 1 o += 1 # Set a[i] to 1 a[i] = 1 # Print the result if (o <= 0): print("Yes") else: print("No") # Driver Codeif __name__ == '__main__': S = "abbbaddzcz" checkPalindrome(S)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to check if a string can be// split into palindromic strings of at// least length 2 by including every// character exactly oncestatic void checkPalindrome(string s){ // Stores the frequency // of each character int[] a = new int[26]; // Store the frequency of // characters with frequencies // 1 and even respectively int o = 0, e = 0; // Traverse the string s for(int i = 0; i < s.Length; i++) a[s[i] - 'a']++; // Iterate over all the characters for(int i = 0; i < 26; i++) { // If the frequency is 1 if (a[i] == 1) o++; // If frequency is even else if (a[i] % 2 == 0 && a[i] != 0) e += (a[i] / 2); } // Print the result if (e >= o) Console.WriteLine("Yes"); else { // Stores the number of characters // with frequency equal to 1 that // are not part of a palindromic string o = o - e; // Iterate over all the characters for(int i = 0; i < 26; i++) { // If o becomes less than 0, // then break out of the loop if (o <= 0) break; // If frequency of the current // character is > 2 and is odd if (o > 0 && a[i] % 2 == 1 && a[i] > 2) { int k = o; // Update the value of o o = o - a[i] / 2; // If a single character // is still remaining if (o > 0 || 2 * k + 1 == a[i]) { // Increment o by 1 o++; // Set a[i] to 1 a[i] = 1; } } } // Print the result if (o <= 0) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// Driver codestatic void Main(){ string S = "abbbaddzcz"; checkPalindrome(S);}}// This code is contributed by sanjoy_62 |
Javascript
<script> // Javascript program for the above approach // Function to check if a string can be // split into palindromic strings of at // least length 2 by including every // character exactly once function checkPalindrome( s ) { // Stores the frequency // of each character let a = [0] // Store the frequency of // characters with frequencies // 1 and even respectively let o = 0, e = 0; // Traverse the string s for (let i = 0; i<s.length; i++) a[s.charCodeAt(i) - 97]++; // Iterate over all the characters for (let i = 0; i < 26; i++) { // If the frequency is 1 if (a[i] == 1) o++; // If frequency is even else if (a[i] % 2 == 0 && a[i] != 0) e += (a[i] / 2); } // Print the result if (e >= o) document.write("Yes") else { // Stores the number of characters // with frequency equal to 1 that // are not part of a palindromic string o = o - e; // Iterate over all the characters for (let i = 0; i < 26; i++) { // If o becomes less than 0, // then break out of the loop if (o <= 0) break; // If frequency of the current // character is > 2 and is odd if (o > 0 && a[i] % 2 == 1 && a[i] > 2) { let k = o; // Update the value of o o = o - a[i] / 2; // If a single character // is still remaining if (o > 0 || 2 * k + 1 == a[i]) { // Increment o by 1 o++; // Set a[i] to 1 a[i] = 1; } } } // Print the result if (o <= 0) document.write("Yes") else document.write("No") } } // Driver Code let S = "abbbaddzcz"; checkPalindrome(S); // This code is contributed by Hritik </script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: 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!
