Permutation of given string that maximizes count of Palindromic substrings
Given a string S, the task is to find the permutation of the string such that palindromic substrings in the string are maximum.
Note: There can be multiple answers for each string.
Examples:
Input: S = “abcb”
Output: “abbc”
Explanation:
“abbc” is the string with maximum number of palindromic substrings.
Palindromic Substrings are – {“a”, “b”, “b”, “c”, “abbc”}
Input: S = “oolol”
Output: “ololo”
Approach: The idea is to sort the characters of the string such that individually and together form a palindromic substring which will maximize the total palindromic substring possible for the permutation of the string.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // permutation of the given string // such that palindromic substrings // is maximum in the string #include <bits/stdc++.h> using namespace std; // Function to find the permutation // of the string such that the // palindromic substrings are maximum string maxPalindromicSubstring(string s){ // Sorting the characters of the // given string sort(s.begin(), s.end()); cout << s; return s; } // Driver Code int main() { // String s string s = "abcb" ; // Function Call maxPalindromicSubstring(s); return 0; } |
Java
// Java implementation to find the // permutation of the given string // such that palindromic substrings // is maximum in the string import java.io.*; import java.util.*; class GFG { // Function to find the permutation // of the string such that the // palindromic substrings are maximum static String maxPalindromicSubstring(String s) { // Convert input string to char array char tempArray[] = s.toCharArray(); // Sorting the characters of the // given string Arrays.sort(tempArray); System.out.println(tempArray); // Return new sorted string return new String(tempArray); } // Driver code public static void main(String[] args) { // String s String s = "abcb" ; // Function Call maxPalindromicSubstring(s); } } // This code is contributed by coder001 |
Python3
# Python3 implementation to find the # permutation of the given string # such that palindromic substrings # is maximum in the string # Function to find the permutation # of the string such that the # palindromic substrings are maximum def maxPalindromicSubstring(s): # Sorting the characters of the # given string res = ''.join( sorted (s)) s = str (res) print (s) # Driver Code if __name__ = = '__main__' : # String s s = "abcb" # Function Call maxPalindromicSubstring(s) # This code is contributed by BhupendraSingh |
C#
// C# implementation to find the // permutation of the given string // such that palindromic substrings // is maximum in the string using System; class GFG{ // Function to find the permutation // of the string such that the // palindromic substrings are maximum static String maxPalindromicSubstring(String s) { // Convert input string to char array char []tempArray = s.ToCharArray(); // Sorting the characters of the // given string Array.Sort(tempArray); Console.WriteLine(tempArray); // Return new sorted string return new String(tempArray); } // Driver code public static void Main() { // String s String s = "abcb" ; // Function Call maxPalindromicSubstring(s); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript implementation to find the // permutation of the given string // such that palindromic substrings // is maximum in the string // Function to find the permutation // of the string such that the // palindromic substrings are maximum function maxPalindromicSubstring(s){ // Sorting the characters of the // given string s.sort(); document.write(s.join( "" )) return s; } // Driver Code // String s var s = "abcb" .split( '' ); // Function Call maxPalindromicSubstring(s); // This code is contributed by noob2000. </script> |
abbc
Time Complexity: O(n*log(n)) where n is the size of the string.
Auxiliary Space: O(1)