أطول سلسلة فرعية دون تكرار
تتبّع آخر مواضع الظهور في نافذة
أطول سلسلة فرعية دون تكرار درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 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). ✅
الأسئلة الشائعة
هل درس «أطول سلسلة فرعية دون تكرار» مجاني؟
نعم — نص درس «أطول سلسلة فرعية دون تكرار» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «أطول سلسلة فرعية دون تكرار»؟
تتبّع آخر مواضع الظهور في نافذة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «أطول سلسلة فرعية دون تكرار»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- مجاميع نافذة ثابتة الحجم
- نافذة متغيرة بمؤشرين
- أطول سلسلة فرعية دون تكرار
- عدّ النوافذ التي تحقق قاعدة