Longest Repeating Character Replacement

Q: מהי סיבוכיות הזמן של החלפת התו החוזר הארוך ביותר?

הפתרון באמצעות חלון אחד רץ בזמן O(n), כאשר n הוא האורך של s : right מבקר בכל אות פעם אחת, ו- left זז לכל היותר פעם אחת בכל צעד. הוא משתמש בזיכרון נוסף של O(1), ב-26 מונים ובכמה מספרים שלמים.

Q: למה אין צורך לעדכן את התדירות המרבית כשהחלון זז?

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

בינוניחלון נע

+10

נתונה לך מחרוזת s של אותיות אנגליות גדולות ומספר שלם k. מותר לך לבחור לכל היותר k מיקומים ב־s ולשנות את האות בכל אחד מהם לכל אות גדולה אחרת.

החזר את האורך של תת־המחרוזת הארוכה ביותר, כלומר רצף של אותיות סמוכות, שמכילה אות אחת שחוזרת על עצמה לאחר השינויים שלך.

פונקציה

characterReplacement(s: string, k: integer) → integer

sstring: המחרוזת של האותיות הגדולות
kinteger: מספר האותיות המרבי שמותר לך לשנות
מחזירהinteger: האורך של תת־המחרוזת הארוכה ביותר של אותה אות חוזרת שאפשר ליצור

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכילה רק אותיות אנגליות גדולות.
0 ≤ k ≤ s.length

דוגמאות

קלט: s = "BAAACAB"k = 1
פלט: 5
הסבר: שנה את C ל־A, ובאינדקסים 1 עד 5 יופיע AAAAA. בשביל שש אותיות נדרשים שני שינויים: באינדקסים 0 עד 5 מופיעים B ו־C, ובאינדקסים 1 עד 6 מופיעים C וה־B האחרון.

קלט: s = "AABBBAB"k = 2
פלט: 6
הסבר: ב־ABBBAB, באינדקסים 1 עד 6, שתי האותיות A הן היחידות שאינן B, ולכן שני שינויים נותנים BBBBBB. המחרוזת כולה מכילה שלוש אותיות A וארבע אותיות B, ולכן היא זקוקה לשלושה שינויים.

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

שאלת המשך

מה משתנה אם s יכולה להכיל כל תו, ולא רק את 26 האותיות הגדולות?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

בדקו כל תת־מחרוזת

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

האינטואיציה

תקן תת־מחרוזת אחת. לאיזו אות היא צריכה להפוך? לאות שכבר מופיעה בתדירות הגבוהה ביותר, כי יש לשנות כל אות אחרת. לכן, תת־מחרוזת באורך len שהאות הנפוצה ביותר בה מופיעה top פעמים דורשת len - top שינויים, ואפשר להגיע אליה כאשר המספר הזה קטן או שווה ל־k.

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

הפתרון איטי כי במחרוזת באורך n יש בערך n²/2 תת־מחרוזות. עבור n = 5 × 10^4 מדובר ב־1.25 × 10^9 בדיקות, הרבה מעבר למה שמגבלת הזמן מאפשרת.

אלגוריתם

הגדר את best ל־0.
עבור כל אינדקס התחלה, אפס את 26 המונים ואת top ל־0.
הזז את end מנקודת ההתחלה ועד לאינדקס האחרון. הוסף את s[end] למונה שלו, והגדל את top אם המונה הזה הוא כעת הגבוה ביותר.
אם end - start + 1 - top ≤ k, אפשר להגיע לתת־המחרוזת: שמור את אורכה אם הוא גדול מ־best.
החזר את best.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

חלון הזזה אחד לכל אות יעד

האינטואיציה

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

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

הרץ זאת עבור כל 26 האותיות ושמור את האורך הטוב ביותר. כל הרצה היא O(n), ולכן מדובר בסך הכול ב־26 מעברים, כ־1.3 × 10^6 צעדים עבור n = 5 × 10^4. זהו זמן ריצה ליניארי, אבל המחרוזת נקראת 26 פעמים, והשיטה עובדת רק משום שקבוצת האותיות קטנה.

אלגוריתם

עבור כל אות יעד מ־A עד Z, מתחילים חלון עם left = 0 ועם others = 0.
מתקדמים עם right לאורך המחרוזת. אם s[right] אינה אות היעד, מוסיפים אחד ל־others.
כל עוד others > k, מקדמים את left, ומחסרים אחד מ־others כשהאות שיוצאת אינה אות היעד.
שומרים את right - left + 1 אם הוא גדול יותר מ־best.
אחרי כל 26 האותיות, מחזירים את best.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

חלון אחד שאף פעם לא מתכווץ

האינטואיציה

טפלו בכל אות בחלון אחד. שמרו בו ספירה של כל אחת מ־26 האותיות, ושל top, הספירה הגבוהה ביותר. החלון זקוק ל־length - top שינויים, ולכן הוא תקין כשהערך הזה לכל היותר k.

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

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

ב־BAAACAB עם k = 1, החלון גדל עד BAAA, ואז BAAAC דורש 2 שינויים, ולכן הוא זז ל־AAAC. הוספת ה־A הבאה מעלה את top ל־4, והחלון גדל ל־AAACA, באורך 5. ה־B האחרונה גורמת לו לזוז פעם נוספת, ולכן התשובה היא 5.

אלגוריתם

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

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

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

קוד החלון קצר, ולכן רוב התשובות השגויות נובעות מנוסחת העלות או מקיצור דרך שרק נראה נכון.

להוסיף k לרצף הארוך ביותר. ב-AAAB עם k = 3 התוצאה היא 6, יותר מאורך המחרוזת. ב-BAAACAB עם k = 1 התוצאה היא 4, אבל השינוי הנכון נמצא באמצע ומחבר שני רצפים לרצף באורך 5.
לספור שינויים ביחס לאות הראשונה בחלון במקום ביחס לאות שמופיעה בו הכי הרבה. החלון BAAA דורש שינוי אחד, לא שלושה.
להחזיר n - left בגרסה שבה החלון יכול להתכווץ. קיצור הדרך הזה תקף רק כשהחלון אף פעם לא מתקצר, כמו בקוד של חלון יחיד כאן. אם הלולאה שלך מכווצת את החלון באמצעות while ומחשבת מחדש את המקסימום האמיתי, יש לשמור משתנה נפרד בשם best.
למדוד את החלון באמצעות right - left. שני הקצוות נמצאים בתוכו, לכן יש להוסיף אחד.
להתייחס אל k = 0 כמקרה מיוחד. כשאין שינויים, כלל החלון כבר מחזיר את הרצף הארוך ביותר של אות אחת.

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

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

הפתרון באמצעות חלון אחד רץ בזמן O(n), כאשר n הוא האורך של s: right מבקר בכל אות פעם אחת, ו-left זז לכל היותר פעם אחת בכל צעד. הוא משתמש בזיכרון נוסף של O(1), ב-26 מונים ובכמה מספרים שלמים.

למה אין צורך לעדכן את התדירות המרבית כשהחלון זז?

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

במה זה שונה ממציאת תת-המחרוזת הארוכה ביותר ללא תווים חוזרים?

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

האם אפשר לפתור את הבעיה הזאת באמצעות חיפוש בינארי?

כן. אם תת־מחרוזת כלשהי באורך L ניתנת להשגה, אז גם כל תת־מחרוזת קצרה יותר בתוכה ניתנת להשגה, ולכן אפשר לבצע חיפוש בינארי על L. עבור כל L, מזיזים חלון קבוע באורך הזה ובודקים אם יש מיקום כלשהו שדורש לכל היותר k שינויים. זה O(n log n), איטי יותר מהפתרון עם חלון יחיד, אבל תשובה סבירה לתת.

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "BAAACAB"
k = 1

צפוי

Longest Repeating Character Replacement

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

בדקו כל תת־מחרוזת

חלון הזזה אחד לכל אות יעד

חלון אחד שאף פעם לא מתכווץ

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

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

בעיות דומות