Partition Labels

+10

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

פונקציה

partitionLabels(s: string) → integer-array

sstring: המחרוזת שיש לחתוך, אותיות קטנות בלבד
מחזירהinteger-array: האורך של כל חלק, משמאל לימין

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכילה רק אותיות אנגליות קטנות.
החלקים שומרים על הסדר שלהם ויחד מרכיבים את כל s, כך שסכום האורכים שלהם שווה ל-s.length.

דוגמאות

קלט: s = "abacdcefe"
פלט: [3, 3, 3]
הסבר: האותיות a נמצאות במקומות 0 ו־2, האותיות c במקומות 3 ו־5 והאותיות e במקומות 6 ו־8, לכן החיתוכים מתבצעים אחרי aba ואחרי cdc. אי אפשר לחתוך שוב אף חלק, כי כל אחד מהם מתחיל ומסתיים באותה אות.

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

בדוק כל פער

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

האינטואיציה

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

לכן בדקו כל פער: אספו את האותיות שמשמאלו ואת אלה שמימינו, וחתכו אם אין אותיות משותפות לשתי הקבוצות. ב־abacdcefe בפער שאחרי aba יש משמאל את a ו־b, ומימין את c, d, e ו־f. אין אותיות משותפות, ולכן חותכים. בפער שאחרי ab יש a משני הצדדים, ולכן לא חותכים.

כל בדיקה קוראת את כל המחרוזת, ויש n-1 פערים, ולכן העבודה כוללת בערך n² קריאות של אותיות. עם 50,000 אותיות מדובר ב־2.5 × 10^9 קריאות, הרבה יותר מדי עבור הבדיקות הגדולות ביותר.

אלגוריתם

מגדירים את start = 0, המקום שבו החלק הנוכחי מתחיל.
עבור כל פער cut מ-1 עד n-1 (הפער ממש לפני s[cut]), מסמנים את האותיות של s[0..cut-1] ואת האותיות של s[cut..n-1].
אם אין אות שמסומנת בשני הצדדים, מוסיפים לתשובה את cut-start ומגדירים start = cut.
אחרי הלולאה, מוסיפים את החלק האחרון, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

מזג את הטווח של כל אות

האינטואיציה

חשבו על כל אות כעל טווח, מהמיקום הראשון שלה ועד למיקום האחרון שלה. חלק שמכיל אות חייב לכסות את כל הטווח הזה. לכן שתי אותיות שהטווחים שלהן חופפים חייבות להיות באותו חלק, והחפיפה מתפשטת: אם a חופף ל־b ו־b חופף ל־c, שלושתם יסתיימו באותו חלק.

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

ב־codingisfun הטווחים לפי הסדר הם c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] ו־u [9, 9]. שלושת הראשונים עומדים בפני עצמם. החל מ־i, כל טווח מתחיל במיקום 10 או לפניו, שבו n מסתיים, ולכן הם מתמזגים ל־[3, 10], חלק של 8 אותיות.

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

אלגוריתם

במעבר אחד על s, שמור את first ואת last, המיקום הראשון והאחרון של כל אות.
עבור שוב על s. כאשר המיקום i הוא המיקום הראשון של האות שלו, המקטע של אותה אות [i, last] הוא הבא לפי סדר ההתחלה.
אם המקטע מתחיל אחרי end של הבלוק הנוכחי, סגור את הבלוק, שאורכו end-start+1, והתחל בלוק חדש ב-i.
כך או כך, הגדר end = max(end, last).
סגור את הבלוק האחרון והחזר את האורכים.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

הרחב כל חלק עד לאות האחרונה שלו

האינטואיציה

המיקומים הראשונים כלל אינם נחוצים. קרא את המחרוזת משמאל לימין ושמור את end, המיקום האחרון הרחוק ביותר של אות כלשהי בחלק הנוכחי. כשאתה קורא אות במיקום i, העותק האחרון שלה חייב להיות גם הוא בחלק הזה, לכן הגדל את end ל-last[s[i]] אם הוא רחוק יותר.

כש-i מגיע ל-end, לכל אות שקראת בחלק הזה יש עותק אחרון במיקום i או לפניו. שום אות אינה חוצה את הרווח שאחרי i, ולכן מותר לחתוך שם. סגור את החלק, שאורכו end-start+1, והתחל את החלק הבא במיקום i+1.

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

ב-abacdcefe המיקומים האחרונים הם a במיקום 2, b במיקום 1, c במיקום 5, d במיקום 4, e במיקום 8 ו-f במיקום 7. קריאת a מציבה את end על 2, b משאירה אותו שם, וב-i = 2 החלק נסגר באורך 3. c מציבה את end על 5 והחלק נסגר במיקום 5, שוב באורך 3. החלק של e נסגר במיקום 8.

אלגוריתם

במעבר אחד, שמור את last[c], המיקום האחרון של כל אות c, במערך בגודל 26.
הגדר start = 0 ו-end = 0.
עבור כל מיקום i, הגדר end = max(end, last[s[i]]).
אם i == end, הוסף את end-start+1 לתשובה והגדר start = i+1.
החזר את האורכים.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

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

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

חיתוך כשמגיעים להופעה האחרונה של האות הנוכחית, במקום ל־end של החלק. ב־abcba, האות c באינדקס 2 היא ההופעה האחרונה שלה, אבל רצף ההופעות של a נמשך עד אינדקס 4, ולכן חיתוך שם יפצל גם את a וגם את b.
טעות של אחד באורך. חלק מ־start עד end, כולל שניהם, מכיל end-start+1 אותיות.
החזרת מיקומי החיתוך במקום האורכים. עבור abacdcefe, התשובה היא [3, 3, 3], ולא [2, 5, 8].
שכחת החלק האחרון כשחותכים בנקודות ההפרדה. אחרי החלק האחרון אין נקודת הפרדה, לכן יש להוסיף n-start לאחר סיום הלולאה.
ציפייה לחלק אחד לכל אות ייחודית. ב־zebraz יש חמש אותיות שונות וחלק אחד בלבד, כי ה־z-ים מחזיקים יחד את כל מה שביניהם.

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

מהי סיבוכיות הזמן של חלוקת תוויות?

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

למה הגישה החמדנית עובדת עבור חלוקת תוויות?

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

האם Partition Labels היא בעיית מיזוג של טווחים?

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

כמה חלקים יכולה Partition Labels להחזיר?

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

Python

def partitionLabels(s):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "abacdcefe"

צפוי

[3, 3, 3]

Partition Labels

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

בדוק כל פער

מזג את הטווח של כל אות

הרחב כל חלק עד לאות האחרונה שלו

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

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

בעיות דומות