Pythonで解く：「a」と「b」の文字列から作成できるユニークな文字列の数を求めるアルゴリズム

「a」と「b」のみで構成された文字列 s があるとします。このとき、「a」はそのまま「a」のままでもよいし、「b」に変換してもかまいません。一方、「b」は一切変更できません。この条件のもとで、作成できるユニークな文字列の総数を求めるのが本問題の目的です。

問題の例

たとえば、入力が s = "baab" の場合、出力は 4 になります。これは、以下の4種類の文字列を作成できるためです。

• "baab"（元のまま）
• "babb"
• "bbab"
• "bbbb"

解法のアプローチ

この問題は非常にシンプルな数学的性質を利用して解けます。「a」はそれぞれ独立に「a」または「b」の2択を選べるため、文字列中の「a」の個数を n とすると、組み合わせの総数は 2ⁿ になります。

具体的には、以下の手順で解きます。

• まず、文字列 s に含まれる 'a' の出現回数をカウントする（counts）
• 次に、2^counts を計算して返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
    def solve(self, s):
        counts = s.count('a')
        total = 2**(counts)
        return total
ob = Solution()
print(ob.solve("baab"))

入力

"baab"

出力

4

計算量について

この解法の時間計算量は O(n)（n は文字列の長さ）で、文字列を一度走査して 'a' をカウントするだけですみます。空間計算量も O(1) と非常に効率的です。べき乗の計算は Python の ** 演算子で高速に処理できます。