K個の異なる文字を含むサイズNの部分文字列を検索するPythonプログラム

NサイズでK個の異なる文字を含む部分文字列が必要な場合、3つの引数を受け取る関数を定義し、「if」文による条件分岐を使って目的の文字列を返すのが一般的なアプローチです。本記事では、その具体的な実装方法をサンプルコードと実行結果、詳細な解説とともにわかりやすく紹介します。

サンプルコード

以下に、実際の実装例を示します。

def generate_my_string(string_size, substring_size, distinct_chars):

   my_string = ""
   count_1 = 0
   count_2 = 0

   for i in range(string_size):
      count_1 += 1
      count_2 += 1

      if (count_1 <= substring_size):
         if (count_2 <= distinct_chars):
            my_string = my_string + chr(96 + count_1)

         else:
            my_string = my_string + 'a'

      else:
         count_1 = 1
         count_2 = 1
         my_string = my_string + 'a'

   return my_string


my_string_size = 8
my_substring_size = 6
K_distinct_chars = 4

print("The string size is :")
print(my_string_size)

print("The substring size is :")
print(my_substring_size)

print("The distinct characters count is :")
print(K_distinct_chars)

print("The resultant string is :")
print(generate_my_string(my_string_size, my_substring_size, K_distinct_chars))

実行結果

The string size is :
8
The substring size is :
6
The distinct characters count is :
4
The resultant string is :
abcdaaab

コードの解説

• まず、「generate_my_string」という名前の関数を定義します。この関数は、文字列全体のサイズ（string_size）、部分文字列のサイズ（substring_size）、異なる文字の種類数（distinct_chars）の3つを引数として受け取ります。

• 関数内では、結果を格納するための空の文字列 my_string を用意し、カウンタとして使用する2つの整数変数 count_1 と count_2 を0で初期化します。

• forループで文字列全体のサイズ分だけ反復処理を行い、各ループで2つのカウンタを1ずつ増やしていきます。

• count_1 が部分文字列のサイズ以下である間は、さらに count_2 が異なる文字数以下かどうかを判定します。条件を満たす場合は chr(96 + count_1) を使って新しい文字を生成して連結します。chr(97) は「a」、chr(98) は「b」のように、ASCIIコードをもとにアルファベット小文字を順番に作り出すことができます。

• count_2 が異なる文字数を超えた場合は、代わりに文字「a」を連結します。

• count_1 が部分文字列のサイズを超えた場合は、両方のカウンタを1にリセットし、再び「a」からパターンを繰り返します。

• 最後に、生成された文字列を戻り値として返します。

• 関数の外側では、文字列サイズ・部分文字列サイズ・異なる文字数の3つの値を定義し、それぞれコンソールに出力します。

• これらの値を引数として関数を呼び出し、その結果をコンソールに表示します。

動作のポイント

上記の例では、文字列サイズ8、部分文字列サイズ6、異なる文字数4を指定しているため、出力は「abcdaaab」となります。この文字列では、長さ6のどの部分文字列を取り出しても、含まれる異なる文字はちょうど4種類（a、b、c、d）になります。

また、このアプローチは文字列を一度だけ走査すればよいため、時間計算量は O(N) となり、補助的なメモリも結果の文字列分だけで済むため、非常に効率的な実装と言えます。