Minimum Window Substring

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

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

Q: מה מונה המונה החסר?

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

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

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

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

+10

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

אם כמה תת־מחרוזות חולקות את האורך הקצר ביותר, החזירו את זו שמופיעה הכי שמאלה. אם אין תת־מחרוזת של s שמכילה את כל התווים של 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, ולכן התשובה היא המחרוזת הריקה.

+17 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

התשובה תלויה במספר המופעים של כל תו בחלון, ולא בסדר שלהם, והחלון הטוב ביותר יכול להתחיל בכל מקום. בדיקת כל נקודת התחלה עם כל נקודת סיום פירושה שיש O(n²) חלונות. הפתרון הוא חלון שהקצוות שלו נעים רק קדימה: הקצה הימני מרחיב אותו עד שהוא מכסה את t, הקצה השמאלי מצמצם אותו כל עוד הוא עדיין מכסה אותה, ומונה אחד של תווים חסרים מגלה לך בצעד אחד אם הוא מכסה את t.

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

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

האינטואיציה

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

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

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

אלגוריתם

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

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

האינטואיציה

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

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

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

אלגוריתם

ספרו את מספר העותקים של 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.

העדכון עולה צעד אחד. כאשר s[right] נכנס וערך need עבורו גדול מ-0, הוא ממלא חוסר, ולכן missing קטן באחד; בכל מקרה need קטן באחד, והוא עשוי לרדת מתחת ל-0 ולהפוך לעודף. כאשר s[left] יוצא, need גדל באחד, ואם עכשיו הוא גדול מ-0, החלון ויתר על עותק שנדרש ב-t, ולכן missing גדל באחד. עודפים באים והולכים בלי להשפיע על missing.

עקוב אחר s = banana, t = aan: בתחילה need הוא a 2, n 1 ו-missing הוא 3. אין צורך ב-b. ה-a הראשון מוריד את missing ל-2, ה-n ל-1, וה-a השני ל-0, כך ש-bana מכיל את t. צמצום החלון מסיר את ה-b העודף ומשאיר את ana, שלושה תווים, שהוא החלון הטוב ביותר החדש. הסרת ה-a הזה מחזירה את missing ל-1. ה-a האחרון מכיל שוב את t עם nana, שמצטמצם ל-ana השני. הוא אינו קצר יותר, ולכן ה-ana השמאלי ביותר נשאר.

כל תו ב-s נכנס לחלון פעם אחת ויוצא ממנו לכל היותר פעם אחת, וכל תזוזה דורשת כמות קבועה של עבודה. בניית need קוראת את t פעם אחת. הריצה כולה היא 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. הקטינו אותו רק כאשר need היה גדול מ-0.
הגדלת missing עבור כל תו שיוצא. הסרה של תו עודף משאירה את החלון מכסה את t; הגדילו אותו רק כאשר need עולה מעל 0.
תיעוד החלון אחרי לולאת הצמצום. עד אז הוא כבר לא מכסה את t. תעדו אותו בתוך הלולאה, לפני הסרת s[left].
החלפת החלון הטוב ביותר כשהחלון החדש באותו אורך. כך מוחזר הימני מבין החלונות הקצרים ביותר; השתמשו בהשוואה של קטן ממש.
שימוש ב-n כאורך לציון "לא נמצא". כאשר התשובה היא כל s, גם האורך שלה הוא n. התחילו מ-n+1 כדי ששני המקרים יהיו שונים.
טבלה של 26 משבצות שמאונדקסות לפי c - 'a'. אותיות גדולות חורגות ממנה. השתמשו במשבצת אחת לכל קוד תו.

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

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

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

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

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

מה מונה המונה החסר?

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

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "mappingtheplan"
t = "nap"

צפוי

"plan"

Minimum Window Substring

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

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

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

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

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

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

בעיות דומות