การหาความยาวของซับสตริงที่ไม่มีตัวอักษรซ้ำด้วย Sliding Window ใน C#

จากสตริงอินพุต ใช้เทคนิค Sliding Window โดยมี pointer สองตัว i และ j ชี้ที่ตัวอักษรเดียวกัน วนลูปผ่านสตริงและเพิ่มลง List หากพบตัวซ้ำ ให้ลบออกจาก List มิฉะนั้นเพิ่มเข้าไป

ตัวอย่าง 1

Input: s = "abcabcbb"

Output: 3

คำอธิบาย: คำตอบคือ "abc" ความยาว 3

ตัวอย่าง 2

Input: s = "bbbbb"

Output: 1

คำอธิบาย: คำตอบคือ "b" ความยาว 1

Time Complexity: O(N)

Space Complexity: O(N)

ตัวอย่างโค้ด

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);
}

ผลลัพธ์

หมายเหตุ: ผลลัพธ์ต้นฉบับแสดง 2 แต่ค่าที่ถูกต้องควรเป็น 3 โค้ดข้างต้นทำงานถูกต้อง