\(O(N!K)\) で解きます。

next_permutationで呼ばれるswapの回数は \(O(N!)\) 回なので、swapの度に回文判定を \(O(K)\) で行うことができれば良いです。
そこで、長さ \(K\) の各部分文字列に対して、自身が回文か否かを \(O(1)\) で更新することにより、回文判定を全体 \(O(K)\) で行うことができます。

長さ \(K\) の部分文字列は全部で \(N-K+1\) 個ありますが、それぞれの文字列に対して以下の情報 \(P\) を管理します。

• 各文字について、対となる文字は同じ文字か否か

この情報は01列として表されるので、 \(P\) は整数として定義できます。
また、1文字の更新に対して \(P\) は明らかに \(O(1)\) で更新できること、 \(P = 2^K - 1\) であることと回文であることは同値なことから、各文字列に対する更新が \(O(1)\) でできることが示せました。

実装例