Given a palindromic string S, the task is to find the count of palindromic strings possible by swapping a pair of character at a time.
Examples:
Input: s = “abba”
Output: 2
Explanation:
1st Swap: abba -> abba
2nd Swap: abba -> abba
All other swaps will lead to a non-palindromic string.
Therefore, the count of possible strings is 2.
Input: s = “aaabaaa”
Output: 15
Naive Approach:
The simplest approach to solve the problem is to generate all possible pair of characters from the given string and for each pair if swapping them generates a palindromic string or not. If found to be true, increase count. Finally, print the value of count.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above-mentioned approach, calculate the frequencies of each character in the string. For the string to remain a palindrome, only the same character can be swapped in the string.
Follow the steps below to solve the problem:
- Traverse the string.
- For every ith character, increase count with the current frequency of the character. This increases the number of swaps the current character can make with its previous occurrences.
- Increase the frequency of the ith character.
- Finally, after complete traversal of the string, print count.
Below is the implementation of above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to return the count of// possible palindromic stringslong long findNewString(string s){ long long ans = 0; // Stores the frequencies // of each character int freq[26]; // Stores the length of // the string int n = s.length(); // Initialize frequencies memset(freq, 0, sizeof freq); for (int i = 0; i < (int)s.length(); ++i) { // Increase the number of swaps, // the current character make with // its previous occurrences ans += freq[s[i] - 'a']; // Increase frequency freq[s[i] - 'a']++; } return ans;}// Driver Codeint main(){ string s = "aaabaaa"; cout << findNewString(s) << '\n'; return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Function to return the count of// possible palindromic Stringsstatic long findNewString(String s){ long ans = 0; // Stores the frequencies // of each character int []freq = new int[26]; // Stores the length of // the String int n = s.length(); // Initialize frequencies Arrays.fill(freq, 0); for (int i = 0; i < (int)s.length(); ++i) { // Increase the number of swaps, // the current character make with // its previous occurrences ans += freq[s.charAt(i) - 'a']; // Increase frequency freq[s.charAt(i) - 'a']++; } return ans;}// Driver Codepublic static void main(String[] args){ String s = "aaabaaa"; System.out.print(findNewString(s));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to implement# the above approach# Function to return the count of# possible palindromic stringsdef findNewString(s): ans = 0 # Stores the frequencies # of each character freq = [0] * 26 # Stores the length of # the string n = len(s) for i in range(n): # Increase the number of swaps, # the current character make with # its previous occurrences ans += freq[ord(s[i]) - ord('a')] # Increase frequency freq[ord(s[i]) - ord('a')] += 1 return ans# Driver Codes = "aaabaaa"print(findNewString(s))# This code is contributed by code_hunt |
C#
// C# Program to implement// the above approachusing System;class GFG{// Function to return the count of// possible palindromic Stringsstatic long findNewString(String s){ long ans = 0; // Stores the frequencies // of each character int []freq = new int[26]; // Stores the length of // the String int n = s.Length; for (int i = 0; i < (int)s.Length; ++i) { // Increase the number of swaps, // the current character make with // its previous occurrences ans += freq[s[i] - 'a']; // Increase frequency freq[s[i] - 'a']++; } return ans;}// Driver Codepublic static void Main(String[] args){ String s = "aaabaaa"; Console.Write(findNewString(s));}}// This code is contributed by sapnasingh4991 |
Javascript
<script> // JavaScript program to implement // the above approach // Function to return the count of // possible palindromic strings function findNewString(s) { var ans = 0; // Stores the frequencies // of each character var freq = new Array(26).fill(0); // Stores the length of // the string var n = s.length; for (let i = 0; i < n; i++) { // Increase the number of swaps, // the current character make with // its previous occurrences ans += freq[s[i].charCodeAt(0) - "a".charCodeAt(0)]; // Increase frequency freq[s[i].charCodeAt(0) - "a".charCodeAt(0)] += 1; } return ans; } // Driver Code var s = "aaabaaa"; document.write(findNewString(s)); </script> |
15
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
