まず、素朴な解法として、すべての \(1 \leq L \leq R \leq N\) を満たす \((L, R)\) について操作後の \(S\) をすべて求めて、それらに元々の \(S\) を加えた集合の中で最も辞書順で小さい文字列を出力する、というアルゴリズムが考えられます。
このアルゴリズムは正しいですが、\((L,R)\) の組が \(\mathrm{O}(N^2)\) 通り考えられて、各文字列の長さは \(N\) なので、全体で \(\mathrm{O}(N^3)\) かかってしまい TLE してしまいます。そこで、うまく工夫して探索する \((L, R)\) の範囲を狭めることを考えてみましょう。

まず、\(S\) が d のみからなる場合は、操作を行わずに \(S\) をそのまま出力するのが最適です。以下では \(S\) が p を含む場合を考えます。
\(S\) の中で最も左にある p の index を \(i\) とおきます。また、\((L, R) = (l, r)\) として操作した場合の最終的な \(S\) を \(g(l, r)\) とおきます。

このとき、次の事実が成り立ちます。

任意の \(g(L, R), L \neq i\) に対して、ある \(R'\) が存在して \(g(i, R') \lt g(L, R)\) が成り立つ。\((\ast)\)

\(i\) と \(L\) の大小関係で場合分けして証明します。

1. \(i \lt L\) の場合

\(i \lt L\) の場合は、\(g(i,i)\) と \(g(L,R)\) を比較してみます。\(g(i,i)\) と \(g(L,R)\) は \(i-1\) 文字目までが一致していて \(i\) 文字目がそれぞれ d と p です。よって \(g(i, i) \lt g(L, R)\) が成り立ちます。

2. \(i \gt L\) の場合

\(i \gt L\) の場合は \(g(i, R)\) と \(g(L, R)\) を比較してみます。 \(g(i, R)\) と \(g(L, R)\) は \(1\) 文字目から \(L-1\) 文字目、および \(R+1\) 文字目から \(N\) 文字目までが一致しているので、残りの部分を比較します。
\(S\) の \(L\) 文字目から \(i-1\) 文字目は仮定よりすべて d なので、\(T = S(i, R)\)、\(U\) を長さ \(i-L\) の d からなる文字列として、各文字列の \(L\) 文字目から \(R\) 文字目は次のようになります。

• \(g(i,R)\) の \(L\) 文字目から \(R\) 文字目: \(U + f(T)\)
• \(g(L,R)\) の \(L\) 文字目から \(R\) 文字目: \(f(U + T) = f(T) + f(U)\)

ここで、\(U + f(T)\) と \(f(T) + f(U)\) それぞれについて、はじめて p が登場する箇所がどこかを考えます。(両者の長さは等しいので、はじめて p が登場する箇所が異なれば文字列の大小を判定できます。)
\(f(T)\) が p を含むかどうかで場合分けします。

a. \(f(T)\) が p を含まない場合

このとき \(U+f(T)\) はすべて d からなる文字列で p を含みません。一方 \(f(U)\) は p のみからなる文字列なので、\(f(T) + f(U)\) の \(\vert T \vert + 1\) 文字目は p です。よって \(U + f(T) \lt f(T) + f(U)\) です。

b. \(f(T)\) の左から \(j\) 文字目に初めて p が登場する場合

\(U+f(T)\) は左から \(\vert U \vert + j\) 文字目にはじめて p が登場します。一方 \(f(T)+f(U)\) は \(j\) 文字目です。よって \(U + f(T) \lt f(T) + f(U)\) です。

よって a. b. 両方の場合で \(U + f(T) \lt f(T) + f(U)\) が確認できました。よって 2. の場合は \(g(i, R) \lt g(L, R)\) が成り立ちます。

以上より、全ての場合について \((\ast)\) が成り立つことが証明できました。\((\ast)\) を利用すると、答えを求めるには \(L = i\) の場合のみを調べればよいことがわかります。なぜならば、すべての \(g(L,R)\) \((L\neq i)\) は、それより小さい文字列 \(g(i,R')\) が存在するため、\(L=i\) の場合のみを調べた場合よりも答えが小さくなることはありえないからです。
これを利用すれば、調べる文字列の個数を \(\mathrm{O}(N^2)\) から \(\mathrm{O}(N)\) に減らすことができて、全体の計算量も \(\mathrm{O}(N^2)\) に落とすことができます。これでこの問題を十分高速に解くことができました。

• 実装例(PyPy)

def f(T):
  U = [c for c in reversed(T)]
  for i in range(len(U)):
    U[i] = 'd' if U[i] == 'p' else 'p'
  return "".join(U)

N = int(input())
S = input()
L = 0
while L != N and S[L] == 'd':
  L += 1
ans = S
for R in range(L + 1, N + 1):
  ans = min(ans, S[:L] + f(S[L:R]) + S[R:])
print(ans)