【競技プログラミング】AtCoder Beginner Contest 363_C問題

# 問題
https://atcoder.jp/contests/abc363/tasks/abc363_c

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1
与えられた文字列 $ S $ の全ての順列を生成し、その中から「長さ $ K $ の回文を部分文字列として含まないもの」の数を求める問題を解く。

---

## 解法手順

### 1. 入力の受け取りと初期処理
```python
n, k = map(int, input().split())
s = input()
```
- $ n $: 文字列 $ S $ の長さ。
- $ k $: 回文の長さ。
- $ s $: 与えられる文字列。

### 2. 全ての文字が異なる場合の特別処理
```python
if len(set(s)) == n:
    ans = 1
    for i in range(1, n + 1):
        ans = ans * i
    print(ans)
    exit()
```
- もし $ S $ の全ての文字が異なる場合（つまり、文字列内に重複がない場合）、全ての順列は異なる。このとき、総順列数は単純に $ n! $（階乗）で求められる。
- この場合、回文を含むかどうかの判定は不要であるため、計算結果を出力して終了する。

### 3. 全順列の生成
```python
a = set(permutations(s))
```
- `itertools.permutations` を用いて、文字列 $ S $ の全ての順列を生成する。
- `set` を使うことで重複する順列を取り除く。

### 4. 回文を含む順列のカウント
```python
count = 0

for i in a:
    for j in range(n - k + 1):
        temp_str = i[j:j + k]
        if temp_str == temp_str[::-1]:
            count += 1
            break
```
- 各順列について、長さ $ K $ の部分文字列（スライス）を全て調べる。
- 部分文字列が回文（逆から読んでも同じ）であれば、その順列は条件に合わないため、カウントする。
- 一度でも回文が見つかった場合、その順列については以降のチェックを省略する（`break`）。

### 5. 条件を満たす順列数の計算と出力
```python
print(len(a) - count)
```
- 全ての順列数（`len(a)`）から、回文を含む順列数（`count`）を引くことで、条件を満たす順列数を求める。
- 最終的な結果を出力する。

---

## 補足説明

### 回文判定について
- 部分文字列 `temp_str` が回文かどうかは、Python のスライス機能 `[::-1]` を使って簡単に判定する。

# 解法手順2

このプログラムは、与えられた文字列 $S$ の全ての順列を生成し、それらの中から「長さ $K$ の回文を部分文字列として含まないもの」の個数を求める問題を解く。

---

## 解法手順

### 1. 入力の受け取りと準備
```python
N, K = map(int, input().split())
S = list(input())
```
- $N$: 文字列 $S$ の長さ。
- $K$: 回文の長さ。
- $S$: 与えられる文字列をリスト形式に変換（リストにすることで要素の並べ替えが容易になる）。

### 2. 辞書順で次の順列を生成する関数 `next_permutation` の実装
```python
def next_permutation(arr) -> bool:
    # 1. 後ろから前に向かって、最初に降順が崩れる位置 (i) を探す
    # 例: arr = [1, 2, 3, 6, 5, 4] の場合、i = 2 (arr[2] = 3)
    i = len(arr) - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1

    # 配列全体が降順の場合（例: [6, 5, 4, 3, 2, 1]）、次の順列は存在しない
    if i == -1:
        return False

    # 2. iより右側で、arr[i] より大きい最小の値を探す位置 (j) を決定
    # この値は、辞書順で次の順列を作るために必要
    j = len(arr) - 1
    while arr[j] <= arr[i]:
        j -= 1

    # 3. arr[i] と arr[j] を交換することで、辞書順で次に進む準備をする
    arr[i], arr[j] = arr[j], arr[i]

    # 4. i+1以降の部分を昇順に並べ替える（これが辞書順で次の最小となる）
    # ソートによって、現在の部分配列を最小化する
    arr[i + 1:] = sorted(arr[i + 1:])

    # 次の順列が生成されたため True を返す
    return True

```
この関数は、現在の配列 `arr` を辞書順で次の順列に変換する。
1. **降順部分を探す**: 配列の右端から左に向かって、最初に降順が崩れる位置を見つける（`i` を求める）。
2. **交換対象を探す**: `i` より右側で、`arr[i]` より大きい最小の値を探し、その位置（`j`）と交換する。
3. **後半部分を昇順に並べ替える**: `i+1` 以降の要素を昇順にソートする。
4. 次の順列が生成されれば `True` を返し、最後の順列の場合には `False` を返す。

---

### 3. 初期処理：辞書順最小の順列からスタート
```python
S.sort()
ans = 0
```
- 入力文字列 $S$ をソートして、辞書順最小の状態からスタートする。
- 条件を満たす順列数をカウントする変数 `ans` を初期化。

---

### 4. 回文判定と初回チェック
```python
has_palind = False
for head in range(N-K+1):
    palind = True
    for j in range(K // 2):
        if S[head+j] != S[head+K-j-1]:
            palind = False
            break
    if palind:
        has_palind = True
        break

if not has_palind:
    ans += 1
```
- 現在の順列 $S$ に対して、長さ $K$ の回文が存在するか判定する。
- 部分文字列が回文かどうかは、左右対称な位置にある文字が一致しているか逐一確認する。
- 回文が存在しない場合（`has_palind == False`）、その順列は条件を満たすため、カウント変数 `ans` をインクリメント。

---

### 5. 全ての辞書順順列をチェック
```python
while next_permutation(S):
    has_palind = False
    for head in range(N-K+1):
        palind = True
        for j in range(K // 2):
            if S[head+j] != S[head+K-j-1]:
                palind = False
                break
        if palind:
            has_palind = True
            break

    if not has_palind:
        ans += 1
```
- `next_permutation(S)` を用いて次の辞書順順列を生成し、それぞれについて回文判定を行う。
- 各順列について、長さ $K$ の回文が存在しない場合のみカウントする。
- 全ての辞書順順列が処理されるまでループする。

---

### 6. 結果の出力
```python
print(ans)
```
条件を満たす全ての順列数（`ans`）を出力する。

---

## 解法全体の流れ

1. 入力文字列 $S$
 を辞書順最小にソートして開始する。
2. 辞書順で全ての可能な並び替え（順列）について、長さ $K$ の回文が存在しないか確認する。
3. 条件を満たす場合のみカウントし、最後にその個数を出力する。