Longest Palindromic Substring

+10

لديك سلسلة نصية s تتكوّن من أحرف إنجليزية صغيرة. أَعِد أطول سلسلة فرعية متناظرة فيها: أطول مقطع من الأحرف المتتالية يُقرأ بالطريقة نفسها من الأمام والخلف. إذا اشتركت عدة سلاسل فرعية في هذا الطول الأكبر، فأَعِد السلسلة التي تبدأ في الموضع الأسبق.

الدالة

longestPalindrome(s: string) → string

sstring: السلسلة النصية بأحرف صغيرة المراد البحث عنها
تُرجعstring: أطول سلسلة فرعية متناظرة في s، والأسبق من اليسار عند وجود عدة سلاسل متساوية الطول

القيود

1 ≤ s.length ≤ 2000
s يحتوي على أحرف إنجليزية صغيرة فقط.
عندما يكون هناك عدة متواليات متناظرة لها أكبر طول، تكون الإجابة هي المتوالية ذات أصغر فهرس بداية.

أمثلة

المدخلات: s = "bananas"
المخرجات: "anana"
الشرح: تُقرأ "anana" بالطريقة نفسها من الطرفين، وتتكوّن من 5 أحرف. لا توجد قطعة أطول تنجح: تبدأ "banana" بالحرف b وتنتهي بالحرف a، وتبدأ "ananas" بالحرف a وتنتهي بالحرف s، وتبدأ الكلمة كاملةً بالحرف b وتنتهي بالحرف s.

المدخلات: s = "xyzzyabba"
المخرجات: "yzzy"
الشرح: "yzzy" و"abba" كلاهما متناظران بطول 4، ولا يوجد شيء أطول. يبدأ "yzzy" عند الفهرس 1، قبل "abba" عند الفهرس 5، لذا يفوز عند التعادل.

المدخلات: s = "abcd"
المخرجات: "a"
الشرح: لا يتساوى أي حرفين، لذا فإن كل متناظرة تتكون من حرف واحد. وأقصى اليسار منها هو "a".

+18 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك إيجاد الإجابة في زمن O(n)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تعكس المتناظرة نفسها حول وسطها، ويكون هذا الوسط إما حرفًا واحدًا (طول فردي، مثل "anana") أو الفجوة بين حرفين متساويين (طول زوجي، مثل "abba"). إن فحص كل مقطع فرعي على حدة يتجاهل هذه البنية وتكلفته O(n³). أما توسيع كل متناظرة إلى الخارج انطلاقًا من وسطها فيعيد استخدام كل مقارنة، ما يخفض زمن البحث إلى O(n²) مع استخدام O(1) من الذاكرة الإضافية.

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

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

الفكرة

يُحدَّد المقطع الجزئي بفهرسه الأول i وفهرسه الأخير j. اختبره باستخدام مؤشرين: قارن s[i] مع s[j]، ثم s[i+1] مع s[j-1]، وهكذا، وتوقف عند أول اختلاف. إذا التقى المؤشران أو تجاوز أحدهما الآخر من دون اختلاف، فالمقطع الجزئي متناظر. احتفظ بأطول مقطع تجده.

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

يفحص هذا جميع المقاطع الجزئية وعددها n(n+1)/2، لذا لا يمكن أن تفوته الإجابة. لكنه بطيء لأن كل اختبار قد يمر على نصف المقطع الجزئي. في سلسلة مكوّنة من 2000 نسخة من a، يكون كل مقطع جزئي متناظرًا، ويستمر كل اختبار حتى المنتصف: نحو n³/12 ≈ 6.7 × 10^8 مقارنة بين الأحرف.

الخوارزمية

ابدأ بالحرف الأول باعتباره الأفضل: البداية 0، والطول 1.
لكل بداية i ولكل نهاية j ≥ i، قارِن الحروف من الطرفين باتجاه المنتصف حتى تختلف أو يلتقي المؤشران.
إذا التقى المؤشران دون اختلاف، فإن s[i..j] متناظرة.
إذا تجاوز طولها j-i+1 الأفضل، فسجّل i وذلك الطول.
أعِد السلسلة الفرعية عند أفضل بداية وبأفضل طول.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

جدول المتناظرات حسب الطول

الفكرة

تنسى طريقة القوة الغاشمة ما تعلّمته. عندما تختبر "anana"، تقارن a مع a ثم n مع n، والمقارنة الثانية هي الاختبار الكامل لـ "nan"، الذي أجرته من قبل. القاعدة التي توفّر العمل: يكون s[i..j] متناظرًا إذا تطابق طرفاه وكان الجزء بينهما، s[i+1..j-1] متناظرًا. مقارنة واحدة وإجابة واحدة مخزنة تحسمان كل مقطع فرعي.

خزّن الإجابات في جدول pal[i][j] واملأه حسب الطول. كل حرف منفرد متناظر. ويكون المقطع الفرعي المؤلف من حرفين متناظرًا عندما يتطابق الحرفان. أما الأطوال الأكبر، فاستخدم القاعدة: الجزء الداخلي أقصر بحرفين، لذا تكون خانته قد مُلئت بالفعل.

في "bananas"، تكون pal[1][5] ("anana") صحيحة لأن s[1] وs[5] كلاهما a، ولأن pal[2][4] ("nan") صحيحة. تزداد الأطوال، وتتحرك بدايات المقاطع من اليسار إلى اليمين، لذا يكون أول مقطع متناظر بطول قياسي جديد هو أيضًا الأيسر بين المقاطع ذات ذلك الطول. تتطلب نحو n²/2 خانة كلفة O(1) لكل منها، لذا يكون الزمن O(n²)؛ أما الثمن فهو الذاكرة: 4 × 10^6 خانة عندما n = 2000.

الخوارزمية

أنشئ جدولًا بحجم n × n باسم pal، واجعل جميع قيمه false.
لكل طول من 1 إلى n، ولكل موضع بداية i بحيث تبقى النهاية j = i+length-1 داخل السلسلة، تحقّق من حرفَي الطرفين.
علِّم الخانة pal[i][j] عندما يتطابقان ويكون الطول 2 أو أقل، أو تكون pal[i+1][j-1] true.
عندما يتجاوز طول خانة معلَّمة الطول الأفضل، سجِّل i والطول.
أعِد السلسلة الفرعية عند أفضل موضع بداية.

def longestPalindrome(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways
    pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

وسّع حول كل مركز

الفكرة

لكل متناظر مركز. يتمركز المتناظر ذو الطول الفردي مثل "anana" حول حرف؛ أما المتناظر ذو الطول الزوجي مثل "abba" فيتمركز حول الفجوة بين حرفيه الأوسطين. تحتوي سلسلة طولها n على n حرفًا و n-1 فجوة، لذا لها 2n-1 مركزًا محتملًا.

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

في "bananas"، ابدأ من الحرف a عند الفهرس 3. الحرفان عند 2 و4 هما n، والحرفان عند 1 و5 هما a، أما الحرفان عند 0 و6 فهما b وs، لذا يتوقف التحرك عند طول 5. البداية هي 3 - (5-1)/2 = 1، وهذا يعطي "anana". وتعمل الصيغة نفسها، center - (length-1)/2 مقربةً إلى الأسفل، مع مراكز الفجوات أيضًا.

تحرك عبر المراكز من اليسار إلى اليمين، ولا تستبدل الأفضل إلا عند العثور على طول أكبر بصرامة. يكون لمتناظرين متساويين في الطول التكافؤ نفسه، ويبدأ المتناظر ذو المركز الأسبق في موضع أسبق، لذا يفوز الأيسر. أسوأ حالة هي سلسلة مكوّنة من حرف واحد مكرر: يتحرك كل مركز حتى يصل إلى الحافة الأقرب، أي نحو n²/2 = 2 × 10^6 خطوة عندما يكون n = 2000، وتقتصر الذاكرة على بضعة أعداد صحيحة.

الخوارزمية

اكتب expand(left, right): ما دام كلا المؤشرين داخل السلسلة والحرفان متطابقين، حرّك left إلى الأسفل وright إلى الأعلى. أعد right-left-1.
لكل مركز من 0 إلى n-1، اختر الأكبر من expand(center, center) وexpand(center, center+1).
إذا تجاوز هذا الطول الأفضل، فعيّن بداية الأفضل إلى center - (length-1)/2 بعد تقريبها إلى الأسفل، وعيّن الطول الأفضل إلى هذا الطول.
أعد السلسلة الفرعية عند بداية الأفضل وبالطول الأفضل.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

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

الفكرة قصيرة، لذا تختبئ الأخطاء في التفاصيل: المراكز بين الحروف، والطول بعد التوسّع، وقاعدة كسر التعادل، والاقتطاع.

التوسّع حول الحروف فقط يُفوّت كل متناظر زوجي. على "abba" يعيد ذلك "a" بدلًا من "abba".
تتوقف الحركة بعد تجاوز كل طرف بخطوة واحدة، لذا يكون المتناظر هو s[left+1..right-1] بطول right-left-1. استخدام right-left+1 يضيف حرفين غير متطابقين.
استبدال الأفضل عند تساوي الطول يعيد المتناظر الأيمن: "abba" بدلًا من "yzzy" في "xyzzyabba".
عند استخدام مركز في فجوة، تكون center - length/2 أبعد من اللازم بمقدار واحد إلى اليسار. في "xyzzyabba"، طول الفجوة بعد الفهرس 2 هو 4، والبداية هي 2 - (4-1)/2 = 1، وليس 0.
تختلف واجهات الاقتطاع: تأخذ substr في C++ وSubstring في C# طولًا، بينما تأخذ substring في JavaScript وsubstring في Java فهرس نهاية.
في الجدول، يؤدي ملء الصفوف حسب البداية تصاعديًا من 0 إلى قراءة pal[i+1][j-1] قبل ملئها. املأ حسب الطول، أو عالج البدايات بدءًا من النهاية.

أسئلة شائعة4

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

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

لماذا يستخدم التوسّع حول المركز 2n-1 مركزًا؟

للمتناظر ذي الطول الفردي حرفٌ أوسط، أما ذو الطول الزوجي فله فجوة وسطى بين حرفين متساويين. تتكوّن السلسلة التي تضم n من الأحرف من n أحرف وn-1 فجوة بين الأحرف المتجاورة. التوسّع انطلاقًا من الأحرف وحدها يفوّت متونًا متناظرة مثل "abba".

ما هي خوارزمية ماناكر؟

يعثر على أطول متناظر حول كل مركز في زمن إجمالي قدره O(n). ويحتفظ بالمتناظر الذي يصل إلى أبعد نقطة جهة اليمين حتى الآن، ويبدأ المركز الواقع داخله من إجابة مركزه المناظر، لذلك لا يُعاد أي حرف للمقارنة من البداية. يجدر بك معرفة اسمه؛ فالتوسّع حول المركز هو الحل الذي يتوقعه القائمون بالمقابلات عادةً.

ما الفرق بين أطول سلسلة فرعية متناظرة وأطول تتابع متناظر؟

السلسلة الفرعية هي مجموعة من الأحرف المتتالية، بينما يمكن للسلسلة الجزئية تخطي بعض الأحرف. في "character"، أطول سلسلة فرعية متناظرة هي "ara"، لكن "carac" سلسلة جزئية متناظرة طولها 5. تُحل نسخة السلسلة الجزئية باستخدام جدول على (i, j) يحذف أحد الطرفين عندما يختلف الطرفان.

Python

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

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

s = "bananas"

المتوقع

"anana"

Longest Palindromic Substring

الدالة

القيود

أمثلة

تلميحات

الحل

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

جدول المتناظرات حسب الطول

وسّع حول كل مركز

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

أسئلة شائعة4

مسائل مشابهة