Permutación de una string dada que maximiza el conteo de substrings palindrómicas

Dada una string S , la tarea es encontrar la permutación de la string tal que las substrings palindrómicas en la string sean máximas.
Nota: Puede haber varias respuestas para cada string. 
Ejemplos: 
 

Entrada: S = “abcb” 
Salida: “abbc” 
Explicación: 
“abbc” es la string con el número máximo de substrings palindrómicas. 
Las substrings palindrómicas son: {“a”, “b”, “b”, “c”, “abbc”}
Entrada: S = “oolol” 
Salida: “ololo” 
 

Enfoque: La idea es clasificar los caracteres de la string de modo que individualmente y juntos formen una substring palindrómica que maximice la substring palindrómica total posible para la permutación de la string.
A continuación se muestra la implementación del enfoque anterior:
 

// 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 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 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# 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

<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

Complejidad de tiempo: O(n*log(n)) donde n es el tamaño de la string.
Espacio Auxiliar: O(1)