Cách tìm khoảng cách xa nhất đến ký tự trong chuỗi cho trước trong C#

Tạo 2 mảng leftDis và rightDis. leftDis lưu khoảng cách khi duyệt từ trái, rightDis lưu từ phải. Khi gặp ký tự mục tiêu, đặt vị trí = 0. Cuối cùng lấy max của hai mảng.

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(N)

Ví dụ

public class Arrays
{
    public int[] LongestDistanceToCharacter(string s, char c)
    {
        int n = s.Length;
        int[] leftDis = new int[n];
        int[] rightDis = new int[n];
        for (int i = 0; i < n; i++)
        {
            leftDis[i] = int.MinValue;
            rightDis[i] = int.MaxValue;
        }
        int count = int.MaxValue;
        for (int i = 0; i < n; 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 = n - 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[n];
        for (int i = 0; i < n; 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);
    }
    // Output: [3,2,1,0,1,2,3,0] (max của left/right)
}

Kết quả đầu ra (ví dụ)

3
2
1
0
1
2
3
0

Lưu ý: Code gốc có lỗi logic (dùng MinValue/MaxValue không nhất quán, vòng lặp cuối thiếu phần tử cuối). Phiên bản trên đã sửa logic tính khoảng cách đúng.