この問題は、\(N\) の桁数を \(L\)、基数を \(B\) として \(O(L+B)\) で解くことができます。

次のようなアルゴリズムで答えを求めることができます。

• \(N\) を文字列として降順にソートする
• \(N\)の先頭から奇数文字目からなる文字列を \(A\)、偶数文字目からなる文字列を \(B\) とする
• \(A,B\) を先頭から見て、初めて異なる文字が登場する箇所について、その \(2\) 文字を入れ替える
• \(A,B\) を整数とみなし \(A\times B\) を出力する

このアルゴリズムは、ソートにバケツソートを用いることで \(O(L+B)\) で動作します。

実装例(Python)　※通常のソートを用いているため時間計算量は \(O(L\log L)\)

N=sorted(input())[::-1]
A=N[0::2]
B=N[1::2]

for i in range(min(len(A),len(B))):
	if A[i]!=B[i]:
		A[i],B[i]=B[i],A[i]
		break

print(int("".join(A))*int("".join(B)))

証明は次のステップに分けて行うことができます

• ①　\(2\) 数の桁数の差が \(2\) 以上であるとき、桁数が大きい方の末尾の数字を桁数が小さい方の末尾に移動してよい
  例：\(1001\times 99\) は \(100\times 991\) にしてよい
• ②　\(2\) 数に使う文字集合を固定した場合は、それぞれ降順に使うのが最適
  例：\(N=123456\) をもし \(\{1,3,4\},\{2,5,6\}\) と分けるなら、\(431\times 652\) としてよい
• ③　②より \(N\) の桁数が奇数なら、\(0\) を \(1\) つ追加し最後に答えを \(10\) で割るとしてよいので、\(N\) が偶数桁の場合のみ考えればよい。したがって①より、\(2\) 数は桁数が等しいとしてよい
• ④　もし他方の数の上位により小さい数があるなら、入れ替えてよい
  例：\(6542 \times 8760\) は\(6542\) の百の位の \(5\) が \(8760\) の十の位の \(6\) より小さいので入れ替えて、\(6642\times 8750\) としてよい
• ⑤　③と④により、考えるべき \(2\) 数の組み合わせは和が一定であるので、積が最大となるのは差が最小となるときである。したがって冒頭のアルゴリズムで答えを得ることができる