// Một chuỗi có n ký tự sẽ có (n + 1) vị trí có thể chèn

// Mỗi vị trí có thể chèn hoặc không => Mỗi vị trí có 2 cách => tối đa có 2^n cách chèn

​

// Với chuỗi k ký tự liên tiếp giống với ký tự c => k + 1 vị trí => k + 2 cách chèn (từ 0 đến k + 1)

// Những vị trí còn lại (không chứa ký tự c) thì lấy 2 mũ

​

using System;

​

public class String

{

    public static int CountDistinctString(string s, char c)

    {

        int result = 1;

        // số ký tự liên tiếp hiện tại giống với ký tự c (k)

        int matchingCharCount = 0;

        // số vị trí có thể chèn còn lại (sau khi trừ đi vị trí giáp với ký tự giống c)

        int remainPos = s.Length + 1;

        for (int i = 0; i < s.Length; i++)

        {

            if (s[i] == c)

            {

                // tăng số lượng số ký tự liên tiếp giống c

                matchingCharCount++;

            }

            else

            {

                // chuỗi ký tự liên tiếp giống c bị ngắt

                if (matchingCharCount > 0)

                {

                    // k + 2 cách chèn với k ký tự c liên tiếp

                    result *= (matchingCharCount + 2);

                    // trừ đi k + 1 vị trí giáp với ký tự giống ký tự c

                    remainPos -= (matchingCharCount + 1);

                }

                matchingCharCount = 0;

            }

        }

        // trong trường hợp ký tự cuối cùng giống c

        if (matchingCharCount > 0)

        {

            result *= (matchingCharCount + 2);

            remainPos -= (matchingCharCount + 1);

        }

        // 2 mũ số vị trí còn lại không giáp với ký tự giống ký tự c

        result *= (int)Math.Pow(2, remainPos);

        return result;

    }

    public static void Main(string[] args)

    {

        Console.WriteLine(CountDistinctString("AB", 'C'));

        Console.WriteLine(CountDistinctString("AA", 'A'));

    }

}

​