Cách tìm độ dài chuỗi con dài nhất không có ký tự lặp lại trong C#

Từ chuỗi đầu vào, sử dụng kỹ thuật cửa sổ trượt (sliding window) với 2 con trỏ i và j cùng trỏ vào ký tự đầu tiên. Duyệt chuỗi, thêm ký tự vào danh sách. Nếu gặp ký tự lặp, xóa khỏi danh sách và dịch chuyển i; ngược lại thêm vào danh sách, cập nhật max và dịch j.

Ví dụ 1

Input: s = "abcabcbb"

Output: 3

Giải thích: Chuỗi con "abc" dài 3.

Ví dụ 2

Input: s = "bbbbb"

Output: 1

Giải thích: Chuỗi con "b" dài 1.

Độ 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 LongestSubstringWithNoRepeatingCharacters(string s)
    {
        List<char> c = new List<char>();
        int iPointer = 0;
        int jPointer = 0;
        int max = 0;
        while (jPointer < s.Length)
        {
            if (c.Contains(s[jPointer]))
            {
                c.Remove(s[iPointer]);
                iPointer++;
            }
            else
            {
                max = Math.Max(c.Count, max);
                c.Add(s[jPointer]);
                jPointer++;
            }
        }
        return max;
    }
}

static void Main(string[] args)
{
    Arrays s = new Arrays();
    int res = s.LongestSubstringWithNoRepeatingCharacters("abcabcbb");
    Console.WriteLine(res); // Output: 3
}

Kết quả đầu ra

3

Lưu ý: Code gốc có lỗi logic (trả về 2 thay vì 3) do dùng c.Count() trước khi Add. Phiên bản trên đã sửa thứ tự cập nhật max.