Minimum Window Substring

Q: מהי סיבוכיות הזמן של Minimum Window Substring?

חלון המונה החסר פועל בזמן O(n + m) , כאשר n ו- m הם האורכים של s ו- t . בניית הטבלה קוראת את t פעם אחת, וכל תו של s נכנס לחלון ויוצא ממנו לכל היותר פעם אחת. הזיכרון הנוסף הוא מונה אחד לכל קוד תו.

Q: במה שונה תת־מחרוזת החלון המינימלי ממציאת אנגרמה במחרוזת?

אנגרמה מכילה בדיוק את האותיות של t , ולכן לחלון שלה יש אורך קבוע של m והוא מחליק צעד אחד בכל פעם. כאן מותרות תווים נוספים, ולכן האורך הוא חלק מהתשובה: החלון גדל עד שהוא מכיל את t , ומתכווץ כל עוד הוא עדיין מכיל אותה.

קשהחלון נע גיבוב

+10

נתונות לך שתי מחרוזות, s ו-t. מצא את תת-המחרוזת הקצרה ביותר של s שמכילה את כל התווים של t, כולל כפילויות: אם t מכילה אות פעמיים, תת-המחרוזת חייבת להכיל אותה לפחות פעמיים. הסדר אינו משנה, ויכולים להופיע גם תווים אחרים.

אם יש כמה תת-מחרוזות קצרות ביותר, החזר את השמאלית ביותר. אם אף אחת מהן אינה מכילה את כל התווים של t, החזר מחרוזת ריקה.

פונקציה

minWindow(s: string, t: string) → string

sstring: המחרוזת שבה יש לחפש
tstring: התווים שהחלון חייב להכיל, כולל חזרות
מחזירהstring: תת־המחרוזת הקצרה ביותר, ואם יש כמה כזו אז השמאלית ביותר, של s שמכילה את כל t, או מחרוזת ריקה

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s ו-t מכילות רק אותיות באנגלית. אותיות גדולות ואותיות קטנות הן תווים שונים.
כאשר יש כמה תתי־מחרוזות שהן הקצרות ביותר, התשובה היא זו השמאלית ביותר; כאשר אין כזו, התשובה היא "".

דוגמאות

קלט: s = "mappingtheplan"t = "nap"
פלט: "plan"
הסבר: החלון הראשון משמאל שמכיל n,‏ a ו־p הוא appin, באורך חמישה תווים. plan מכילה את שלושתם בארבעה תווים, ואף רצף של שלושה תווים אינו מכיל את שלושתם.

קלט: s = "banana"t = "aan"
פלט: "ana"
הסבר: t מבקש שני עותקים של a ועותק אחד של n. ana באינדקס 1 מכיל בדיוק את זה. ana שני מתחיל באינדקס 3, והראשון משמאל הוא שנבחר.

קלט: s = "Coddy"t = "cd"
פלט: ""
הסבר: האות C ב־Coddy היא אות גדולה, כלומר תו שונה מ־c. אף תת־מחרוזת אינה מכילה c קטנה, לכן התשובה היא המחרוזת הריקה.

שאלת המשך

כש־t מכילה מעט אותיות ו־s ארוכה, לרוב s אין שום חשיבות. האם תוכל לגרום לחלון לקפוץ רק בין מיקומים שמכילים אות של t?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

רק הספירות בחלון חשובות, ולא הסדר שלהן. הזז את הקצה הימני עד שהחלון מכסה את t, ואז את הקצה השמאלי כל עוד הוא עדיין מכסה אותו; אף אחד מהקצוות לא חוזר לאחור. מונה של התווים החסרים מאפשר לך לדעת בצעד אחד אם החלון מכסה את t.

הרחיבו חלון מכל נקודת התחלה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

קובעים נקודת התחלה ומגדילים את החלון בתו אחד בכל פעם, תוך ספירת המופעים של כל תו. אחרי כל צעד, בודקים כל אחת מ־u האותיות שבהן משתמשת t. נקודת הסיום הראשונה שעוברת את הבדיקה נותנת את החלון הקצר ביותר שמכסה את הדרוש מנקודת ההתחלה הזאת, ולכן עוצרים שם. עוברים על נקודות ההתחלה משמאל לימין, ורק חלון קצר יותר ממש מחליף את הטוב ביותר, כך שבמקרה של שוויון נשמר החלון השמאלי ביותר.

אם אין חלון מתאים, בכל נקודת התחלה קוראים עד לסוף של s: בערך n²/2 צעדים, כלומר 1.25 × 10^9 עבור n = 5 × 10^4.

אלגוריתם

ספור את מספר ההופעות של כל אות ש-t דורשת.
עבור כל start, אפס את טבלת הספירה והזז את end ימינה, תוך הוספת s[end].
כשהחלון מכיל מספיק מכל אות, שמור אותו אם הוא קצר יותר מהטוב ביותר, ועבור להתחלה הבאה.
החזר את החלון הטוב ביותר, או את "" אם אף חלון לא הכיל את כל האותיות שב-t.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

חלון הזזה שבודק כל אות

האינטואיציה

הוספת תווים לחלון שמכיל את כל התווים הדרושים משאירה אותו כזה, והסרת תווים מחלון שחסר בו משהו משאירה אותו חסר. לכן, כשההתחלה זזה ימינה, הסוף של החלון הקצר ביותר שמכיל את כל התווים הדרושים לעולם לא זז שמאלה.

לא מפספסים אף חלון. ניקח את החלון הטוב ביותר, מ־L עד R. כדי ש־left יעבור את L לפני ש־right יגיע ל־R, חלון קצר יותר שמתחיל ב־L היה צריך להכיל את t. לכן, כש־right מגיע ל־R, הכיווץ מזיז את left עד L ומתעד את החלון.

כל קצה זז לכל היותר n פעמים, אבל כל בדיקה קוראת עד u ספירות: O(n·u).

אלגוריתם

ספרו את מספר העותקים של t הנדרשים; הגדירו left = 0 ואת האורך הטוב ביותר בתור n+1.
עבור כל right, הוסיפו את s[right] לספירות שבחלון.
כל עוד יש מספיק עותקים מכל אות ב-t, שמרו את החלון אם הוא קצר יותר ממש, הסירו את s[left] והתקדמו עם left.
החזירו את החלון הטוב ביותר, או את "" אם האורך הטוב ביותר עדיין n+1.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

חלון הזזה עם מונה חסרים

האינטואיציה

החליפו את הסריקה במספר אחד. נסמן ב־need[c] את מספר העותקים של c ש־t דורשת, פחות מספר העותקים שבחלון; ערך שלילי פירושו עותפים מיותרים. נסמן ב־missing את מספר העותקים שעדיין חסרים בחלון, שמתחיל באורך של t. החלון מכיל בדיוק את t כאשר missing הוא 0.

תו שנכנס כאשר need שלו גדול מ־0 ממלא פער, ולכן missing קטן. תו שהסרתו מעלה את need שלו מעל 0 יוצר פער, ולכן missing גדל. עותפים מיותרים אינם משפיעים עליו. עבור banana עם t = aan, missing מגיע ל־0 לראשונה ב־bana, והסרת ה־b המיותר משאירה את ana עדיין מכיל.

כל תו נכנס ויוצא פעם אחת בעלות קבועה: זמן O(n + m), עם טבלה אחת של 128 מונים.

אלגוריתם

מלא את need בספירות של t; הגדר את missing לאורך של t, את left = 0 ואת האורך הטוב ביותר ל־n+1.
עבור כל right: אם need[s[right]] גדול מ־0, הקטן את missing; לאחר מכן הקטן את need[s[right]].
כל עוד missing הוא 0, תעד את החלון אם אורכו קצר יותר באופן מוחלט. הגדל את need[s[left]]; אם כעת הוא גדול מ־0, הגדל את missing. קדם את left.
החזר את החלון הטוב ביותר, או "" אם האורך הטוב ביותר עדיין n+1.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

מלכודות ומקרי קצה

ספירת אותיות במקום מופעים. t = aan דורשת שני מופעים של a, ולכן ban לא מכסה אותה.
שינוי missing עבור כל תו שנכנס או יוצא. כך a עודף נספר, ו-missing יכול להגיע ל-0 כשהחלון עדיין חסר את n.
החלפת החלון הטוב ביותר כשיש שוויון באורך. בדוגמה השנייה, כך מוחזר ana שבאינדקס 3.
שימוש ב-n כאורך של „לא נמצא”. כשהתשובה היא כל s, גם האורך שלה הוא n; התחילו מ-n+1.
טבלה של 26 מקומות שמאונדקסים לפי c - 'a'. אותיות גדולות, כמו בדוגמה השלישית, נמצאות מחוץ לטווח שלה.

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

מהי סיבוכיות הזמן של Minimum Window Substring?

חלון המונה החסר פועל בזמן O(n + m), כאשר n ו-m הם האורכים של s ו-t. בניית הטבלה קוראת את t פעם אחת, וכל תו של s נכנס לחלון ויוצא ממנו לכל היותר פעם אחת. הזיכרון הנוסף הוא מונה אחד לכל קוד תו.

למה הקצה השמאלי אף פעם לא זז בחזרה?

הקצה השמאלי עובר על פני מיקום רק לאחר שהחלון שמתחיל בו כיסה את t, והחלון הזה היה החלון הקצר ביותר שמכסה את t מנקודת ההתחלה הזאת. כל חלון מאותה נקודה שמסתיים מאוחר יותר הוא ארוך יותר, ולכן חזרה לאחור לעולם לא תמצא תשובה טובה יותר.

במה שונה תת־מחרוזת החלון המינימלי ממציאת אנגרמה במחרוזת?

אנגרמה מכילה בדיוק את האותיות של t, ולכן לחלון שלה יש אורך קבוע של m והוא מחליק צעד אחד בכל פעם. כאן מותרות תווים נוספים, ולכן האורך הוא חלק מהתשובה: החלון גדל עד שהוא מכיל את t, ומתכווץ כל עוד הוא עדיין מכיל אותה.

def minWindow(s, t):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

s = "mappingtheplan"
t = "nap"

הפלט הצפוי

"plan"

Minimum Window Substring

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

הרחיבו חלון מכל נקודת התחלה

חלון הזזה שבודק כל אות

חלון הזזה עם מונה חסרים

מלכודות ומקרי קצה

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

בעיות דומות