Hay muchas formas de hacerlo y dependerán de las funciones, las estructuras,... que quieras usar. Básicamente dependerá de tu algoritmo.
También tendrás que tener en cuenta ciertas precondiciones como si conoces la cantidad de dígitos diferentes existentes o si todos los dígitos iguales aparecerán seguidos,...
Puedes usar una estructura para guardar un valor y sus repeticiones. Crear un array de esta estructura y guardar todos los valores, ordenar dicho array y después crear la nueva cadena a partir de esos resultados.
Puedes usar una cola con prioridad (puedes usar la de la STL de C++). Y es altamente recomendable no solo para esto sino para todos tus programas que tengas en claro tu lenguaje de programación. En C++ no se usa malloc/free sino new/delete. Tienes los strings para facilitarte el trabajo con cadenas y tienes las clases en vez de las estructuras.