Reorganizar la string para maximizar el número de substrings palindrómicas

Dada una string S que consta solo de caracteres en minúsculas (az), la tarea es imprimir una nueva string reorganizando la string de tal manera que maximice el número de substrings palindrómicas. En caso de múltiples respuestas, imprima cualquiera. 
Nota: aunque algunas substrings coincidan, cuéntalas tantas veces como aparezcan en la string obtenida.
Ejemplos:
 

Entrada: s = “aabab” 
Salida: ababa 
string “ababa” tiene 9 substrings palindrómicas: “a”, “b”, “a”, “b”, “a”, “aba”, “bab”, “aba” , “ababa”.
Entrada: s = “aa” 
Salida: aa 
La string dada tiene el máximo número de substrings palindrómicas posibles, “a”, “a” y “aa”. 
 

El problema puede parecer complejo, pero al resolver varios casos y tener observaciones conducirá a una solución fácil. 
Una solución simple es ordenar la string e imprimirla. Ordenar toma O(N * log N) .
Una solución eficiente es contar la frecuencia de cada carácter usando una array freq[] y luego construir la string usando la array freq[]. 
A continuación se muestra la implementación del enfoque anterior.
 

// C++ program to rearrange the
// string such to maximize the
// number of palindromic substrings
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the newString
string newString(string s)
{
    // length of string
    int l = s.length();
 
    // hashing array
    int freq[26] = { 0 };
 
    // iterate and count
    for (int i = 0; i < l; i++) {
        freq[s[i] - 'a'] += 1;
    }
 
    // resulting string
    string ans = "";
 
    // form the resulting string
    for (int i = 0; i < 26; i++) {
 
        // number of times character appears
        for (int j = 0; j < freq[i]; j++) {
 
            // append to resulting string
            ans += (char)(97 + i);
        }
    }
 
    return ans;
}
 
// Driver Code
int main()
{
 
    string s = "aabab";
 
    cout << newString(s);
 
    return 0;
}

// Java program to rearrange the
// string such to maximize the
// number of palindromic substrings
 
 
public class GFG {
     
    // Function to return the newString
    static String newString(String s)
    {
        // length of string
        int l = s.length();
 
        // hashing array
        int freq[] = new int [26] ;
 
        // iterate and count
        for (int i = 0; i < l; i++) {
            freq[s.charAt(i) - 'a'] += 1;
        }
 
        // resulting string
        String ans = "";
 
        // form the resulting string
        for (int i = 0; i < 26; i++) {
 
            // number of times character appears
            for (int j = 0; j < freq[i]; j++) {
 
                // append to resulting string
                ans += (char)(97 + i);
            }
        }
 
        return ans;
    }
 
 
    // Driver code
    public static void main(String args[])
    {
           String s = "aabab";
            System.out.println(newString(s));
    }
    // This Code is contributed by ANKITRAI1
}

# Python3 program to rearrange the
# string such to maximize the
# number of palindromic substrings
 
# Function to return the newString
def newString(s):
 
    # length of string
    l = len(s)
 
    # hashing array
    freq = [0] * (26)
 
    # iterate and count
    for i in range(0, l):
        freq[ord(s[i]) - ord('a')] += 1
 
    # resulting string
    ans = ""
 
    # form the resulting string
    for i in range(0, 26):
 
        # number of times character appears
        for j in range(0, freq[i]):
 
            # append to resulting string
            ans += chr(97 + i)
     
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    s = "aabab"
    print(newString(s))
 
# This code is contributed by Rituraj Jain

// C# program to rearrange the
// string such to maximize the
// number of palindromic substrings
using System;
class GFG
{
 
// Function to return the newString
static String newString(string s)
{
    // length of string
    int l = s.Length;
 
    // hashing array
    int[] freq = new int [26];
 
    // iterate and count
    for (int i = 0; i < l; i++)
    {
        freq[s[i] - 'a'] += 1;
    }
 
    // resulting string
    string ans = "";
 
    // form the resulting string
    for (int i = 0; i < 26; i++)
    {
 
        // number of times character appears
        for (int j = 0; j < freq[i]; j++)
        {
 
            // append to resulting string
            ans += (char)(97 + i);
        }
    }
 
    return ans;
}
 
 
// Driver code
public static void Main()
{
    string s = "aabab";
    Console.Write(newString(s));
}
}
 
// This code is contributed
// by ChitraNayal

<script>
    // Javascript program to rearrange the
    // string such to maximize the
    // number of palindromic substrings
     
    // Function to return the newString
    function newString(s)
    {
        // length of string
        let l = s.length;
 
        // hashing array
        let freq = new Array(26);
        freq.fill(0);
 
        // iterate and count
        for (let i = 0; i < l; i++)
        {
            freq[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
        }
 
        // resulting string
        let ans = "";
 
        // form the resulting string
        for (let i = 0; i < 26; i++)
        {
 
            // number of times character appears
            for (let j = 0; j < freq[i]; j++)
            {
 
                // append to resulting string
                ans += String.fromCharCode(97 + i);
            }
        }
 
        return ans;
    }
 
     let s = "aabab";
    document.write(newString(s));
     
    // This code is contributed by divyeshrabadiya07.
</script>

aaabb

Complejidad temporal : O(N) 
Espacio auxiliar: O(26)