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

מהי סיבוכיות הזמן של Longest Substring Without Repeating Characters?

חלון ההזזה פועל בזמן 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

בעיות דומות