yukicoder 1376 Simple LPS Problem
とりあえず$ N \leq 8の場合は$ O(2^N N^2)の全探索をすることにより解くことができる.
以後, $ 9 \leq Nの場合について考えてみる. ここで$ N = 9の場合について先ほどの全探索で実験してみると, 必ず$ 4 \leq f(S)となることがわかる. よって$ 9 \leq Nかつ$ K \leq 3のとき条件を満たす$ Sは存在しない.
逆に$ 4 \leq Kの場合は必ず存在する. $ 1を$ K回繰り返した後, (つまり自明に回文を作る)$ 010011(4文字以上の回文にならない)を繰り返した文字列の先頭$ N文字とすればよい.
実装例: https://yukicoder.me/submissions/618529