C#で文字列内の特定の文字までの最長距離を求める方法を解説

文字列の中に含まれる特定の文字に対して、各位置からその文字までの最長距離を求める問題は、左右両方向からの走査を組み合わせることで効率的に解くことができます。本記事では、C#を用いた具体的な実装方法と、その仕組みをわかりやすく解説します。

アルゴリズムの基本的な考え方

この問題を解く鍵となるのは、leftDis と rightDis という役割の異なる2つの配列を用意することです。

• leftDis … 右から左へ走査したときの距離の値を格納する配列
• rightDis … 左から右へ走査したときの距離の値を格納する配列

走査の途中で対象の文字に出会ったら、その位置の値を配列に記録し、カウントをリセットします。それ以外の位置では、直前の文字からの距離を表すカウントを1ずつ増やしながら値を更新していきます。最終的なステップとして、両方の配列の同じインデックス同士を比較し、大きい方の値を採用することで結果を求めます。

計算量について

時間計算量：O(n)
文字列を左右の方向からそれぞれ1回ずつ走査するだけなので、線形時間で処理が完了します。

空間計算量：O(n)
距離を保存するために、入力と同じサイズの補助配列を2つ使用します。

C#による実装例

以下のコードは、文字列 "lovecode" と文字 'e' を使って、各位置から 'e' までの距離を計算する例です。

public class Arrays{
    public int[] LongestDistanceToCharacter(string s, char c){
        int stringLength = s.Length;
        int[] leftDis = new int[s.Length];
        int[] rightDis = new int[s.Length];
        leftDis = Enumerable.Range(0, s.Length).Select(n => int.MinValue).ToArray();
        rightDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray();
        int count = int.MaxValue;
        for (int i = 0; i < rightDis.Length; i++){
            if (s[i] == c){
                count = 0;
                rightDis[i] = count;
            }
            else{
                if (count != int.MaxValue){
                    count++;
                    rightDis[i] = count;
                }
            }
        }
        count = int.MaxValue;
        for (int i = leftDis.Length - 1; i >= 0; i--){
            if (s[i] == c){
                count = 0;
                leftDis[i] = count;
            }
            else{
                if (count != int.MaxValue){
                    count++;
                    leftDis[i] = count;
                }
            }
        }
        int[] ans = new int[stringLength];
        for (int i = 0; i < stringLength - 1; i++){
            ans[i] = Math.Max(leftDis[i], rightDis[i]);
        }
        return ans;
    }
}

static void Main(string[] args){
    Arrays s = new Arrays();
    string ss = "lovecode";
    char c = 'e';
    var res = s.LongestDistanceToCharacter(ss, c);
    foreach (var item in res){
        Console.WriteLine(item);
    }
}

出力結果

[2147483647,2147483647,2147483647,0,3,2,3,0]

出力の読み方

先頭の3つの要素が 2147483647（int型の最大値）になっているのは、これらの位置より左側に 'e' が存在せず、右方向走査の初期値がそのまま残るためです。また、インデックス3と7には 'e' 自身が存在するため、距離は 0 となります。

なお、最後の集計ループが i < stringLength - 1 という条件で回っているため、末尾の要素は配列の初期値 0 のままになっている点には注意してください。すべての要素を確実に計算したい場合は、ループ条件を i < stringLength に変更するとよいでしょう。