จากอินพุตสตริงที่กำหนด ให้ใช้เทคนิคหน้าต่างบานเลื่อนโดยมีตัวชี้ 2 ตัว i และ j ทั้ง i และ j จะชี้ไปที่อักขระเดียวกันในสตริง ข้ามผ่านสตริงและเพิ่มลงในรายการ หากพบอักขระที่ซ้ำกัน ให้ลบออกจากรายการ มิฉะนั้น ให้ต่อท้ายรายการ
ตัวอย่างที่ 1
ป้อนข้อมูล − s ="abcabcbb"
ผลลัพธ์ − 3
คำอธิบาย − คำตอบคือ "abc" โดยมีความยาวเท่ากับ 3
ตัวอย่างที่ 2
ป้อนข้อมูล − s ="bbbbb"
ผลลัพธ์ − 1
คำอธิบาย − คำตอบคือ "b" โดยมีความยาวเท่ากับ 1
ความซับซ้อนของเวลา − O(N)
ความซับซ้อนของอวกาศ − 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){
int res = s.LongestSubstringWithNoRepeatingCharacters("abcabcbb");
Console.WriteLine(res);
} ผลลัพธ์
2
