Longest Palindrome

Q: מהי סיבוכיות הזמן של Longest Palindrome?

זמן 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 נותנים 4 אותיות. חמש אותיות נותרות בחוץ, וכל אחת מהן יכולה לעמוד באמצע: 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).

מהי סיבוכיות הזמן של Longest Palindrome?

זמן 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"

הפלט הצפוי