思いついたものメモ

※あくまでメモ・信頼性は全くない

• N文字のK種類の文字からなる文字列strで、「i番目以降に文字cが出てくる最初のインデックスを各i,cについて全て求める」は後ろからやるとO(NK)

int dp[K][N+1];
for(int c = 0; c < K; c ++) {
  dp[c][N] = INF;
  for(int i = N-1; i >= 0; i ++) {
    dp[c][i] = str[i] == c ? 0 : min(dp[c][i+1]+1, INF);
  }
}

• 「長さNの文字列1をちょうど(exactly)k回swapして文字列2に出来るか？」は

int t = N-閉路の数; //dfsで
if(t <= k && ((有効な、状態を行き来するswapが存在する && t%その閉路長 == k%その閉路長) || 一つでも、文字列を変えないswapが存在する))

という感じ？
「有効な、状態を行き来するswapが存在する」は普通は一つでも有効なswapが存在したら%2でおｋ
考えたらちょうどkの長さでノードからノードへいけるか？という問題だな。どういう名前なんでしょう？