回文部分文字列の最大長がkを超えない文字列を生成するC++プログラム

問題の概要

2つの整数 n と k が与えられたとします。ここで、'a'、'b'、'c' の3種類の文字のみを使用して長さ n の文字列 S を生成することを考えます。ただし、S に含まれる回文となっている部分文字列の最大の長さは、k を超えてはいけません。

例えば、入力が n = 3、k = 2 の場合、出力は "aab" となります。文字列の長さは3であり、長さ2の回文部分文字列 "aa" を含んでいるためです(他の答えも存在します)。

解法のアプローチ

この問題は実は非常にシンプルに解くことができます。'a'、'b'、'c' の3文字をこの順番で繰り返す文字列(例: "abcabc...")を生成すればよいのです。

このような文字列では、隣り合う2文字が同じになることはなく、1文字を挟んで同じ文字が現れることもありません。そのため、長さ2以上の回文部分文字列は一切存在せず、回文部分文字列の最大長は常に1になります。したがって、k が1以上である限り、この方法で常に条件を満たす文字列を生成できます。

手順

この問題を解くために、以下の手順に従います。

S := 空文字列
j := 0
i := 0 から i < n まで、i を1ずつ増やしながら繰り返す:
    S := S に (j + 'a' のASCIIコード) で表される文字を連結
    j := (j + 1) mod 3
S を返す

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

string solve(int n, int k) {
    string S = "";
    int j = 0;
    for (int i = 0; i < n; i++) {
        S += j + 'a';
        j = (j + 1) % 3;
    }
    return S;
}
int main() {
    int n = 3;
    int k = 2;
    cout << solve(n, k) << endl;
}

入力

3, 2

出力

abc

出力の解説

出力された "abc" は長さ3の文字列で、回文となっている部分文字列は "a"、"b"、"c" の長さ1のものだけです。回文部分文字列の最大長は1であり、これは k = 2 を超えていないため、条件を満たす正解の一つとなっています。

このアルゴリズムの計算量は文字列の生成に O(n)、使用する記憶域も O(n) であり、非常に効率的です。