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") הוא true כי s[1] ו־s[5] הן שתיהן a, וגם pal[2][4] ("nan") הוא true. האורכים עולים, ומתחילים משמאל לימין, ולכן הפלינדרום הראשון באורך שובר שיא חדש הוא גם השמאלי ביותר באורך הזה. בערך 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 מקבלים אינדקס סיום.
בטבלה, מילוי השורות לפי נקודת התחלה בסדר עולה קורא את pal[i+1][j-1] לפני שהוא מתמלא. מלאו לפי אורך, או עברו על נקודות ההתחלה מהסוף.

שאלות נפוצות4

מהי סיבוכיות הזמן של תת־המחרוזת הפלינדרומית הארוכה ביותר?

הרחבה סביב מרכזים דורשת זמן O(n²) וזיכרון נוסף O(1). גם גישת הטבלה דורשת זמן O(n²), אבל היא זקוקה לזיכרון O(n²), ובדיקת כל תת־מחרוזת דורשת זמן O(n³). האלגוריתם של Manacher מגיע ל־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

בעיות דומות