Longest Substring Without Repeating Characters

Q: ما الفرق بين السلسلة الجزئية والتتابع الجزئي؟

السلسلة الفرعية هي مجموعة من الأحرف المتجاورة، مثل ode في coddycode . أما التسلسل الفرعي فقد يتجاوز بعض الأحرف، مثل cdy . تتطلب هذه المسألة سلسلة فرعية، ولهذا تنجح نافذة ذات حدّين.

متوسطالنافذة المنزلقة التجزئة

+10

لديك سلسلة نصية s. أوجد أطول سلسلة فرعية، وهي مجموعة من الأحرف المتجاورة، لا يتكرر فيها أي حرف، وأعِد طولها.

تُعد الأحرف الكبيرة والصغيرة أحرفًا مختلفة، لذا فإن a وA لا يُعدّان تكرارًا.

الدالة

lengthOfLongestSubstring(s: string) → integer

sstring: السلسلة المراد البحث عنها
تُرجعinteger: طول أطول سلسلة فرعية لا تحتوي على أحرف مكررة

القيود

1 ≤ s.length ≤ 5 × 10⁴
يحتوي s على أحرف إنجليزية فقط (صغيرة وكبيرة) وأرقام.
الأحرف الكبيرة والأحرف الصغيرة أحرف مختلفة.

أمثلة

المدخلات: s = "coddycode"
المخرجات: 5
الشرح: يحتوي ycode على خمسة أحرف مختلفة. إضافة d قبله تعطي dycode، مع تكرار d مرتين، ولا توجد سلسلة أخرى من خمسة أحرف أو أكثر تتجنب التكرار.

المدخلات: s = "racecar"
المخرجات: 4
الشرح: كلٌّ من race وecar يتكوّن من أربعة أحرف مختلفة. تحتوي كل مجموعة من خمسة أحرف على الحرف نفسه مرتين.

المدخلات: s = "a1b2a3b"
المخرجات: 5
الشرح: تُعَدّ الأرقام محارف أيضًا، لذا يحتوي 1b2a3 على خمسة محارف مختلفة. ويحتوي كلا التتابعين ذوي الطول ستة على حرف a ثانٍ أو حرف b ثانٍ.

سؤال إضافي

ما الذي ستغيّره إذا كان بإمكان s أن يحتوي على أي محرف Unicode بدلًا من الحروف والأرقام؟

الحل

احتفظ بنافذة: حدّان يحيطان بمقطع لا يحتوي على أحرف مكررة. يقرأ الحد الأيمن كل حرف مرة واحدة، ولا يتحرك الحد الأيسر إلا إلى الأمام، لذا تعثر جولة واحدة، عند كل نهاية، على أطول مقطع خالٍ من التكرار ينتهي عندها.

تحقّق من كل سلسلة فرعية

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

جرّب كل موضعَي بداية ونهاية، واختبر كل سلسلة فرعية بإضافة محارفها إلى مجموعة حتى يكون أحدها موجودًا فيها بالفعل. يُختبر كل مرشح، لذا لا يمكن تفويت أطول سلسلة صالحة.

هناك نحو n²/2 سلسلة فرعية، أي 1.25 × 10^9 عندما تكون n = 5 × 10^4، وقد يقرأ الاختبار ما يصل إلى n محرفًا: O(n³). هنا يتوقف الاختبار بعد 63 محرفًا على الأكثر، لأن السلسلة لا تحتوي إلا على 62 محرفًا مختلفًا، لكن ذلك يترك أكثر من مليار اختبار.

الخوارزمية

عيّن best إلى 0.
لكل فهرس بداية، كرّر عبر كل فهارس النهاية من البداية إلى نهاية السلسلة.
أضف أحرف الجزء الفرعي واحدًا تلو الآخر إلى مجموعة فارغة، وتوقّف عند أول حرف موجود مسبقًا في المجموعة.
إذا لم يتكرر أي حرف وكان الجزء الفرعي يتجاوز best، فخزّن طوله.
أعِد best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

النافذة المنزلقة باستخدام مجموعة

الفكرة

إذا لم يتكرر abc، فإن اختبار abcd يتطلب سؤالًا واحدًا: هل d موجود ضمن a وb وc؟ تجيب مجموعة أحرف النافذة عن ذلك دفعة واحدة.

حرّك right خطوة واحدة في كل مرة. إذا كان الحرف الجديد موجودًا في المجموعة، فأزل الأحرف من اليسار حتى تزول نسخته السابقة، ثم أضِفه وقِس. لا تحذف الأحرف إلا عند الضرورة، لذا تكون النافذة لكل قيمة من right أطول سلسلة متصلة بلا تكرار تنتهي عند ذلك الموضع، وتنتهي أفضل سلسلة فرعية في موضع ما. يدخل كل حرف المجموعة مرة واحدة ويغادرها مرة واحدة على الأكثر: O(n).

الخوارزمية

ابدأ بمجموعة فارغة، وleft = 0 وbest = 0.
حرّك right عبر كل فهرس.
ما دام s[right] موجودًا في المجموعة، فأزِل s[left] وحرّك left خطوة واحدة إلى الأمام.
أضف s[right] إلى المجموعة.
إذا كانت right - left + 1 أكبر من best، فاحفظها.
أعِد best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

نافذة منزلقة تقفز إلى الفهرس الذي شوهد آخر مرة

الفكرة

أنت تعرف بالفعل أين يجب أن يستقر left: بعد نسخة المحرف الجديد السابقة مباشرةً. خزّن آخر فهرس لكل محرف، في خريطة أو مصفوفة تحتوي على خانة لكل رمز محرف، وسيقفز left إلى هناك بخطوة واحدة.

لا تقفز إلا عندما يكون ذلك الفهرس عند left أو بعده. فالنسخة الأقدم موجودة بالفعل خارج النافذة، والقفز إليها سيحرّك left إلى الخلف. النافذة في كل خطوة هي نفسها التي يبنيها إصدار المجموعة، والآن يتطلب كل محرف عملية بحث واحدة ومقارنة واحدة وكتابة واحدة.

الخوارزمية

أنشئ خريطة فارغة تربط الأحرف بآخر فهرس لها، واجعل left = 0 وbest = 0.
حرّك right عبر كل فهرس، واقرأ الحرف ch عنده.
إذا كان آخر ظهور لـ ch عند left أو بعده، فاجعل left يساوي ذلك الفهرس زائد واحد.
سجّل right بوصفه آخر فهرس لـ ch.
إذا كانت قيمة right - left + 1 أكبر من best، فاحفظها.
أعِد best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

أخطاء شائعة وحالات حدّية

تحريك left إلى الخلف. في abba، يكون حرف a الأسبق عند الفهرس 0 خارج النافذة بالفعل عند الوصول إلى حرف a الأخير. يؤدي الانتقال إلى الفهرس 1 إلى إعادة حرف b الثاني إلى النافذة، ويعطي 3 بدلًا من 2.
احتساب طول النافذة على أنه right - left. كلا الطرفين داخلها، لذا أضف واحدًا.
تحويل السلسلة إلى أحرف صغيرة أولًا. يُعدّ a وA حرفين مختلفين هنا، لذا طول aA هو 2.
القياس فقط عند ظهور حرف مكرر. السلسلة التي لا تحتوي على أحرف مكررة، مثل z، لا تؤدي إلى ذلك أبدًا، فتكون الإجابة 0.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة أطول سلسلة فرعية دون أحرف مكررة؟

تعمل النافذة المنزلقة بزمن O(n)، حيث إن n هو طول السلسلة النصية: تقرأ الحافة اليمنى كل محرف مرة واحدة، ولا تتحرك الحافة اليسرى إلا إلى الأمام. المساحة الإضافية هي O(k)، حيث إن k هو عدد المحارف المختلفة التي يمكن أن تحتوي عليها السلسلة النصية، وهو 62 هنا.

هل ينبغي أن تستخدم خريطة تجزئة أم مصفوفة للفهرس الأخير؟

كلاهما يستغرق زمنًا قدره O(n). عند التعامل مع مجموعة صغيرة وثابتة من الأحرف، كما في هذه الحالة، تتجنب المصفوفة المفهرسة برمز الحرف التجزئة وتكون أسرع.

ما الفرق بين السلسلة الجزئية والتتابع الجزئي؟

السلسلة الفرعية هي مجموعة من الأحرف المتجاورة، مثل ode في coddycode. أما التسلسل الفرعي فقد يتجاوز بعض الأحرف، مثل cdy. تتطلب هذه المسألة سلسلة فرعية، ولهذا تنجح نافذة ذات حدّين.

def lengthOfLongestSubstring(s):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

s = "coddycode"

الإخراج المتوقع

Longest Substring Without Repeating Characters

الدالة

القيود

أمثلة

تلميحات

الحل

تحقّق من كل سلسلة فرعية

النافذة المنزلقة باستخدام مجموعة

نافذة منزلقة تقفز إلى الفهرس الذي شوهد آخر مرة

أخطاء شائعة وحالات حدّية

أسئلة شائعة3

مسائل مشابهة