Given a string s and an integer X, our task is to find the number of distinct palindromic strings of length X from the given string.
Examples:
Input: s = “aaa”, X = 2
Output: 1
Explanation:
Here all the characters of the string is the same so we can only make a one different string {aa} of length 2.Input: s = “aabaabbc”, X = 3
Output: 6
Explanation:
To make a palindromic string of length 3 we have 6 possible strings aaa, aba, aca, bab, bcb, bbb.
Naive Approach: The naive method is to generate all the possible subsequence of length X, then check if that subsequence forms a palindrome or not.
Time Complexity: O(2N)
Auxiliary Space: O(X)
Efficient Approach: The idea is to find the frequency of all the characters of the string. Count the different numbers of the characters we can put at the particular position and decrease the number of count by 2 because for palindromic string the position (i) and (X – i) will be the same. If the length of X is odd then we have to put the only single char at that position X/2.
Below is the implementation of the above approach:
C++
// C++ implementation to count different// palindromic string of length X// from the given string S#include <bits/stdc++.h>using namespace std;// Function to count different// palindromic string of length X// from the given string Slong long findways(string s, int x){ // Base case if (x > (int)s.length()) return 0; long long int n = (int)s.length(); // Create the frequency array int freq[26]; // initialize frequency array with 0 memset(freq, 0, sizeof freq); // Count the frequency in the string for (int i = 0; i < n; ++i) freq[s[i] - 'a']++; multiset<int> se; for (int i = 0; i < 26; ++i) if (freq[i] > 0) // Store frequency of the char se.insert(freq[i]); long long ans = 1; for (int i = 0; i < x / 2; ++i) { long long int count = 0; for (auto u : se) { // check the frequency which // is greater than zero if (u >= 2) // No. of different char we can // put at the position of // the i and x - i count++; } if (count == 0) return 0; else ans = ans * count; // Iterator pointing to the // last element of the set auto p = se.end(); p--; int val = *p; se.erase(p); if (val > 2) // decrease the value of the char // we put on the position i and n - i se.insert(val - 2); } if (x % 2 != 0) { long long int count = 0; for (auto u : se) // different no of char we can // put at the position x/2 if (u > 0) count++; ans = ans * count; } // Return total no of // different string return ans;}// Driver codeint main(){ string s = "aaa"; int x = 2; cout << findways(s, x); return 0;} |
Java
// Java implementation to count different// palindromic string of length X from the// given string Simport java.util.Arrays;import java.util.HashSet;import java.util.Set;class GFG{// Function to count different// palindromic string of length X// from the given string Sstatic int findways(String s, int x) { // Base case if (x > s.length()) return 0; int n = s.length(); // Create the frequency array int[] freq = new int[26]; // initialize frequency array with 0 Arrays.fill(freq, 0); // Count the frequency in the string for(int i = 0; i < n; ++i) freq[s.charAt(i) - 'a']++; // multiset<int> se; Set<Integer> se = new HashSet<>(); for(int i = 0; i < 26; ++i) if (freq[i] > 0) // Store frequency of the char se.add(freq[i]); int ans = 1; for(int i = 0; i < x / 2; ++i) { int count = 0; for(int u : se) { // Check the frequency which // is greater than zero if (u >= 2) // No. of different char we can // put at the position of // the i and x - i count++; } if (count == 0) return 0; else ans = ans * count; // Iterator pointing to the // last element of the set int p = (int)se.toArray()[se.size() - 1]; int val = p; se.remove(p); if (val > 2) // Decrease the value of the char // we put on the position i and n - i se.add(val - 2); } if (x % 2 != 0) { int count = 0; for(int u : se) // Different no of char we can // put at the position x/2 if (u > 0) count++; ans = ans * count; } // Return total no of // different string return ans;}// Driver codepublic static void main(String[] args) { String s = "aaa"; int x = 2; System.out.println(findways(s, x));}}// This code is contributed by sanjeev2552 |
Python3
# Python3 implementation to count # different palindromic string of# length X from the given string S# Function to count different# palindromic string of length X# from the given string Sdef findways(s, x): # Base case if(x > len(s)): return 0 n = len(s) # Create the frequency array # initialize frequency array with 0 freq = [0] * 26 # Count the frequency in the string for i in range(n): freq[ord(s[i]) - ord('a')] += 1 se = set() for i in range(26): if(freq[i] > 0): # Store frequency of the char se.add(freq[i]) ans = 1 for i in range(x // 2): count = 0 for u in se: # Check the frequency which # is greater than zero if(u >= 2): # No. of different char we can # put at the position of # the i and x - i count += 1 if(count == 0): return 0 else: ans *= count # Iterator pointing to the # last element of the set p = list(se) val = p[-1] p.pop(-1) se = set(p) if(val > 2): # Decrease the value of the char # we put on the position i and n - i se.add(val - 2) if(x % 2 != 0): count = 0 for u in se: # Different no of char we can # put at the position x/2 if(u > 0): count += 1 ans = ans * count # Return total no of # different string return ans# Driver codeif __name__ == '__main__': s = "aaa" x = 2 print(findways(s, x))# This code is contributed by Shivam Singh |
C#
// C# implementation to count different// palindromic string of length X from the// given string Susing System;using System.Collections.Generic;class GFG { // Function to count different // palindromic string of length X // from the given string S static int findways(string s, int x) { // Base case if (x > s.Length) return 0; int n = s.Length; // Create the frequency array int[] freq = new int[26]; // Count the frequency in the string for (int i = 0; i < n; ++i) freq[s[i] - 'a']++; // multiset<int> se; HashSet<int> se = new HashSet<int>(); for (int i = 0; i < 26; ++i) if (freq[i] > 0) // Store frequency of the char se.Add(freq[i]); int ans = 1; for (int i = 0; i < x / 2; ++i) { int count = 0; foreach(int u in se) { // Check the frequency which // is greater than zero if (u >= 2) // No. of different char we can // put at the position of // the i and x - i count++; } if (count == 0) return 0; else ans = ans * count; // Iterator pointing to the // last element of the set int[] arr = new int[se.Count]; se.CopyTo(arr); int p = arr[se.Count - 1]; int val = p; se.Remove(p); if (val > 2) // Decrease the value of the char // we put on the position i and n - i se.Add(val - 2); } if (x % 2 != 0) { int count = 0; foreach(int u in se) // Different no of char we can // put at the position x/2 if (u > 0) count++; ans = ans * count; } // Return total no of // different string return ans; } // Driver code static public void Main() { string s = "aaa"; int x = 2; Console.WriteLine(findways(s, x)); }}// This code is contributed by dharanendralv23 |
Javascript
<script>// Javascript implementation to count different// palindromic string of length X// from the given string S// Function to count different// palindromic string of length X// from the given string Sfunction findways(s, x){ // Base case if (x > s.length) return 0; var n = s.length; // Create the frequency array var freq = Array(26).fill(0); // Count the frequency in the string for (var i = 0; i < n; ++i) freq[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; var se = []; for (var i = 0; i < 26; ++i) if (freq[i] > 0) // Store frequency of the char se.push(freq[i]); var ans = 1; for (var i = 0; i < x / 2; ++i) { var count = 0; se.forEach(u => { // check the frequency which // is greater than zero if (u >= 2) // No. of different char we can // put at the position of // the i and x - i count++; }); if (count == 0) return 0; else ans = ans * count; se.sort((a,b)=>a-b) var val = se[se.length-1] // Iterator pointing to the // last element of the set se.pop(); if (val > 2) // decrease the value of the char // we put on the position i and n - i se.push(val - 2); } if (x % 2 != 0) { var count = 0; se.forEach(u => { // different no of char we can // put at the position x/2 if (u > 0) count++; }); ans = ans * count; } // Return total no of // different string return ans;}// Driver codevar s = "aaa";var x = 2;document.write( findways(s, x));// This code is contributed by noob2000.</script> |
Output:
1
Time Complexity: O(N + 26 * X)
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!
