สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ
ติดตามตำแหน่งที่พบล่าสุดในหน้าต่าง
สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
โจทย์หน้าต่างสุดคลาสสิก
จงหาสตริงย่อยที่ ยาวที่สุดและไม่มีอักขระซ้ำกัน นี่เป็นโจทย์หน้าต่างเลื่อนยอดนิยมที่พบได้ในระบบตรวจคำตอบแทบทุกแห่ง 🔤
กับดักของการลองทุกกรณี
การตรวจสอบสตริงย่อยทุกส่วนเพื่อหาค่าซ้ำมีต้นทุนประมาณ O(n^2) หรือมากกว่านั้น สำหรับสตริงยาว วิธีนี้ช้าเกินไปมาก จึงต้องใช้การกวาดผ่านที่ฉลาดกว่า
หน้าต่างของอักขระที่ไม่ซ้ำ
รักษาหน้าต่างที่มีอักขระ แตกต่างกันอยู่เสมอ ขยายหน้าต่างทางขวา และเมื่อพบอักขระซ้ำ ให้หดหน้าต่างจากทางซ้ายจนกว่าอักขระซ้ำนั้นจะหายไป
จำตำแหน่งล่าสุด
เก็บ ดัชนีล่าสุดของอักขระแต่ละตัวไว้ในพจนานุกรม วิธีนี้ทำให้ทราบได้ทันทีว่าอักขระที่ซ้ำเคยปรากฏล่าสุดที่ใดขณะสแกน
last = {}
left = 0
best = 0สแกนอักขระแต่ละตัว
วนลูปโดยใช้ right ผ่านสตริง พร้อมอ่านทั้งดัชนีและ อักขระในแต่ละขั้น วิธีนี้จะขับเคลื่อนหน้าต่างไปข้างหน้าทีละตำแหน่ง
for right, ch in enumerate(s):ขยับตัวชี้ left แบบก้าวกระโดด
หากอักขระนั้นเคยปรากฏ ภายในหน้าต่างปัจจุบัน ให้เลื่อน left ไปยังตำแหน่งถัดจากตำแหน่งล่าสุดของอักขระนั้น วิธีนี้จะนำอักขระซ้ำออกได้ในครั้งเดียว
if ch in last and last[ch] >= left:
left = last[ch] + 1อัปเดตและวัดความยาว
บันทึก ตำแหน่งใหม่ของอักขระนี้ จากนั้นหน้าต่างตั้งแต่ left ถึง right จะไม่มีอักขระซ้ำ ความยาวของหน้าต่างคือ right ลบ left บวกหนึ่ง
last[ch] = right
best = max(best, right - left + 1)เหตุใดการตรวจสอบนี้จึงสำคัญ
การตรวจสอบ last[ch] >= left เป็นสิ่งจำเป็น หากไม่มีการตรวจสอบนี้ ตำแหน่งเก่าที่อยู่นอกหน้าต่างจะทำให้ left ย้อนกลับอย่างไม่ถูกต้อง
เวลาเชิงเส้น พื้นที่เชิงเส้น
อักขระแต่ละตัวจะถูกเยี่ยมชมครั้งเดียว และ left จะเคลื่อนไป ข้างหน้าเท่านั้น ดังนั้นการสแกนจึงใช้เวลา O(n) ส่วนพจนานุกรมใช้พื้นที่ตามจำนวนอักขระที่แตกต่างกัน
กรณีขอบที่ต้องครอบคลุม
สตริง ว่างมีคำตอบเป็นศูนย์ และสตริงที่มีอักขระเดิมซ้ำกันมีคำตอบเป็นหนึ่ง ตรวจสอบทั้งสองกรณีก่อนส่งคำตอบเพื่อหลีกเลี่ยง WA ที่อาจเกิดขึ้นโดยไม่ทันระวัง
รูปแบบที่นำกลับมาใช้ได้
แผนที่ตำแหน่งล่าสุดร่วมกับตัวชี้ left ที่กระโดดข้าม สามารถประยุกต์ใช้กับโจทย์เรื่อง การไม่ซ้ำกันได้อีกมาก เช่น หน้าต่างที่มีอักขระซ้ำได้ไม่เกินหนึ่งตัว
ตรวจสอบอย่างรวดเร็ว
คุณติดตามดัชนีล่าสุดของอักขระแต่ละตัวขณะสแกนหาสตริงย่อยที่ไม่ซ้ำและยาวที่สุด
ทบทวน
เลื่อนหน้าต่างของอักขระที่ไม่ซ้ำ เก็บ ตำแหน่งล่าสุดของแต่ละตัว แล้วขยับ left ข้ามอักขระซ้ำ วิธีนี้แก้โจทย์คลาสสิกนี้ได้ในเวลา O(n) ✅
คำถามที่พบบ่อย
บทเรียน “สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ”
ติดตามตำแหน่งที่พบล่าสุดในหน้าต่าง คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ผลรวมหน้าต่างขนาดคงที่
- หน้าต่างแปรผันด้วยตัวชี้สองตัว
- สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ
- นับหน้าต่างที่เป็นไปตามกฎ