\(S'\) は \(S\) の並び替えであるので、各英小文字の文字数は同数です。

また、公式解説にも載っているように、 \(S'\) は \(S\) の各文字を昇順に並び替えたものです。

従って、 \(c=\) a,b,…z の順番に \(c\) を \(S\) に含まれる数だけ出力するという操作をすることでこの問題を解くことができます。計算量は \(O(N)\) です。

実装例 (Java)

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        for (int i = 0; i < 26; i++) {
            for (char c : s) {
                if ('a' + i == c) {
                    System.out.print(c);
                }
            }
        }
        sc.close();
    }
}

また、最初に各文字が \(S\) に何回ずつ登場するかを保持する配列を持っておくことでより高速に解くことができます。

実装例 (Java)

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int[] a = new int[26];
        for (char c : s) {
            a[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < a[i]; j++) {
                System.out.print((char) ('a' + i));
            }
        }
        sc.close();
    }
}