【C#】文字列の前半と後半が同じ文字セットを持つかどうかを判定する方法

この記事では、C#を使って文字列の前半と後半が同じ文字セット（使用されている文字の種類）を持っているかどうかを判定する方法を解説します。カウンター配列を活用したシンプルで効率的なアプローチを紹介します。

アルゴリズムの考え方

まず、チェック対象の文字列を設定します。

string s = "timetime";

次に、文字列の前半と後半それぞれの出現文字を数えるためのカウンター配列を2つ用意します。ここでは英小文字を想定しているため、26個の要素を持つ整数配列を使用します。

int []one = new int[MAX_CHAR];
int []two = new int[MAX_CHAR];

続いて、文字列の先頭から進むポインター i と、末尾から進むポインター j を使い、前半と後半を同時に走査しながら各文字の出現回数をカウントします。

for (int i = 0, j = l - 1; i < j; i++, j--) {
    one[str[i] - 'a']++;
    two[str[j] - 'a']++;
}

最後に、2つのカウンター配列を比較します。すべての文字について出現回数が一致していれば、前半と後半は同じ文字セットを持つと判定できます。なお、文字列の長さが1の場合は前半と後半が存在しないため、そのまま true を返します。

サンプルコード

以下は、C#で文字列の前半と後半が同じ文字セットを持つかどうかを判定する完全なコード例です。

例

using System;
class Demo {
    static int MAX_CHAR = 26;
    static bool findSameCharacters(string str) {
        int []one = new int[MAX_CHAR];
        int []two = new int[MAX_CHAR];
        int l = str.Length;
        if (l == 1)
        return true;
        for (int i = 0, j = l - 1; i < j; i++, j--) {
            one[str[i] - 'a']++;
            two[str[j] - 'a']++;
        }
        for (int i = 0; i < MAX_CHAR; i++)
        if (one[i] != two[i])
        return false;
        return true;
    }
    public static void Main() {
        string str = "timetime";
        if (findSameCharacters(str))
        Console.Write("Yes: Two halves are same!");
        else
        Console.Write("No! Two halves are not same!");
    }
}

出力

Yes: Two halves are same!

この例では、文字列 "timetime" の前半「time」と後半「time」がどちらも同じ文字（t・i・m・e）で構成されているため、「同じ文字セットである」という結果が出力されます。この手法の計算量は O(n) であり、文字列の長さに比例して一度だけ走査するため、非常に効率的です。