Longest Palindrome

Q: ما هو التعقيد الزمني لإيجاد أطول سلسلة متناظرة؟

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

سهلالتجزئة الخوارزميات الجشعة

+10

لديك سلسلة نصية s تتكون من أحرف كبيرة وصغيرة. أعد ترتيب أحرفها لبناء أطول متناظر يمكنك تكوينه، وأعِد طول ذلك المتناظر. يمكنك وضع الأحرف بأي ترتيب وترك بعضها، لكن يمكنك استخدام كل حرف عددًا لا يتجاوز عدد مرات ظهوره في s.

الأحرف الكبيرة والصغيرة مختلفة، لذا فإن Aa ليس متناظرًا.

الدالة

longestPalindrome(s: string) → integer

sstring: الأحرف التي يمكنك استخدامها، الكبيرة والصغيرة
تُرجعinteger: طول أطول متناظرة يمكنك تكوينها من تلك الأحرف

القيود

1 ≤ s.length ≤ 5 × 10⁴
s يحتوي على أحرف إنجليزية فقط، من a إلى z ومن A إلى Z.
ليس عليك استخدام كل حرف.

أمثلة

المدخلات: s = "coddyCode"
المخرجات: 5
الشرح: يظهر o مرتين وd ثلاث مرات، أما البقية فتظهر مرة واحدة. زوج من o وزوج من d وحرف واحد متبقٍ في الوسط تعطي طولًا يساوي 5، على سبيل المثال doCod.

المدخلات: s = "Aa"
المخرجات: 1
الشرح: A وa حرفان مختلفان، لذلك لا يوجد أي زوج. الحرف الواحد بمفرده متناظر، وطوله 1.

المدخلات: s = "xxxyyy"
المخرجات: 5
الشرح: يشكّل حرفا x وحرفا y أزواجًا، ويتوسطها حرف واحد متبقٍ، كما في xyxyx. أما حرف y الأخير فليس له شريك، ويبقى خارجًا.

سؤال إضافي

هل يمكنك إرجاع أطول متناظرة واحدة نفسها، مع طولها، في زمن O(n)؟

تلميحات

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

فُتح 0 من 3

الحل

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

رتّب العناصر المتجاورة واجمعها في أزواج

الفكرة

يجعل الترتيب الحروف المتطابقة متجاورة، بحيث يكون كل زوج جنبًا إلى جنب. في xxxyyy، يتطابق حرفا x عند الفهرسين 0 و1: خذ الزوج وانتقل بمقدار موضعين. عند الفهرس 2، يختلف x عن y، لذا يبقى ذلك الـx بلا زوج وتنتقل موضعًا واحدًا. يشكّل حرفا y عند الفهرسين 3 و4 زوجًا ثانيًا، ويبقى حرف y الأخير منفردًا. يمنحك الزوجان 4، بالإضافة إلى حرف واحد في الوسط: 5.

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

الخوارزمية

رتّب أحرف s.
مرّ على الأحرف المرتّبة باستخدام فهرس i. إذا كان الحرفان عند i وi+1 متساويين، فأضف 2 إلى الطول وتقدّم موضعين؛ وإلا فتقدّم موضعًا واحدًا.
إذا كان الطول أقل من عدد الأحرف، فأضف 1 للحرف الأوسط.
أعِد الطول.

def longestPalindrome(s):
    letters = sorted(s)
    n = len(letters)
    length = 0
    i = 0
    while i + 1 < n:
        if letters[i] == letters[i + 1]:
            length += 2  # a pair: one copy on each side of the middle
            i += 2
        else:
            i += 1
    # A letter left without a partner can stand alone in the middle
    if length < n:
        length += 1
    return length

عُدَّ كلَّ حرف

الفكرة

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

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

تمريرة واحدة على s تملأ العدّادات، وتمريرة واحدة على العدّادات الـ128 تجمع الأزواج: زمن O(n) ومساحة إضافية O(1) (وO(n) في R، التي تحوّل s أولًا إلى متجه من الرموز).

الخوارزمية

أنشئ 128 عدادًا واجعل قيمتها 0، وأضف 1 إلى عداد كل حرف من s.
لكل عداد، أضف إلى الطول العددَ مقربًا إلى الأسفل إلى أقرب عدد زوجي.
إذا كان الطول أقل من طول s، فهذا يعني أن أحد الأعداد فردي، لذا أضف 1 للحرف الأوسط.
أعِد الطول.

def longestPalindrome(s):
    counts = [0] * 128  # one counter per character code, so 'A' and 'a' differ
    for ch in s:
        counts[ord(ch)] += 1
    length = 0
    for count in counts:
        length += count // 2 * 2  # every pair fits, one copy on each side
    # Fewer letters used than s has: some count is odd, so one letter can go in the middle
    if length < len(s):
        length += 1
    return length

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

تجاهل الأعداد الفردية تمامًا. الحرف الذي يظهر 3 مرات يوفّر زوجًا واحدًا: xxxyyy يعطي 5، وليس 1.
إضافة 1 لكل عدد فردي. لا يتسع الوسط إلا لحرف واحد، لذا فإن xxxyyy يعطي 5، وليس 6.
اعتبار A وa الحرف نفسه. لا يحتوي Aa على أي زوج، لذا فالإجابة هي 1، وليس 2.
تحديد حجم العدادات من a إلى z فقط. رموز الأحرف الكبيرة تتراوح بين 65 و90 وتقع خارج هذا النطاق؛ استخدم رمز الحرف الكامل فهرسًا.

أسئلة شائعة3

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

هنا يمكنك إعادة ترتيب الأحرف، لذا فالأعداد وحدها هي المهمة، ويحلّ العدّ المسألة في O(n). أما مسألة أطول مقطع فرعي متناظر فتطلب متناظرًا يظهر بالفعل كتتابع من الأحرف المتجاورة، وتحتاج إلى طريقة أخرى، مثل التوسّع حول كل مركز. بالنسبة إلى abab، إجابة هذه المسألة هي 4 (abba)، وإجابة نسخة المقطع الفرعي هي 3 (aba).

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

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

هل يجب عليك استخدام كل حرف من s؟

لا. يُدرَج كل زوج، وفي المنتصف يُدرَج حرف واحد غير مزدوج كحد أقصى. لذا يكون الجواب هو طول s عندما يكون عدد الحروف ذات التكرار الفردي حرفًا واحدًا على الأكثر، وإلا فيكون طول s ناقص عدد الحروف ذات التكرار الفردي، زائد 1.

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

اختبار #1

اختبار #2

اختبار #3

وسيط

s = "coddyCode"

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