First Unique Character in a String

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

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

קלגיבוב

+10

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

פונקציה

firstUniqChar(s: string) → integer

sstring: המחרוזת לחיפוש, אותיות קטנות בלבד
מחזירהinteger: האינדקס של האות הראשונה שמופיעה בדיוק פעם אחת, או ‎-1 אם אין כזו

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכילה רק אותיות קטנות באנגלית (a עד z).

דוגמאות

קלט: s = "coddycode"
פלט: 4
הסבר: ב־coddycode האותיות c ו־o מופיעות פעמיים, d מופיעה שלוש פעמים ו־e מופיעה פעם אחת, באינדקס 8. אבל גם y מופיעה פעם אחת, באינדקס 4, והיא מופיעה ראשונה, לכן התשובה היא 4.

קלט: s = "swiss"
פלט: 1
הסבר: ב־swiss האות s מופיעה שלוש פעמים. האות w באינדקס 1 מופיעה פעם אחת, וכך גם i באינדקס 2; הראשונה מביניהן מנצחת, ולכן התשובה היא 1.

קלט: s = "aabbcc"
פלט: -1
הסבר: כל אות ב־aabbcc מופיעה פעמיים, לכן אין תו ייחודי והתשובה היא -1.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

חפש עותק שני של כל אות

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

האינטואיציה

עבור על המיקומים משמאל. עבור המיקום i, סרוק את המחרוזת כולה כדי למצוא מיקום אחר j שבו מופיעה אותה אות. אם אין כזה, s[i] ייחודית, ומכיוון שאתה מתקדם משמאל, היא האות הייחודית הראשונה: החזר את i. ב־coddycode, בכל אחד מהמיקומים 0 עד 3 נמצאת התאמה, ואילו במיקום 4, האות y, לא נמצאת התאמה.

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

עצירה במציאת העותק הראשון עוזרת ברוב המחרוזות, אבל לא בכולן. כאשר כל אות מופיעה ברצף ארוך אחד, כמו 2000 אותיות a, ואז 2000 אותיות b וכן הלאה, הסריקה של כל אות עוברת על פני כל הרצפים הקודמים לפני שהיא מוצאת עותק. עבור n = 5 × 10^4 מדובר ביותר ממיליארד השוואות, וזה איטי מדי עבור הבדיקות הגדולות ביותר.

אלגוריתם

עבור כל אינדקס i משמאל לימין:
סרקו כל אינדקס j שאינו i, ועצרו בראשון שבו s[j] שווה ל־s[i].
אם אין j כזה, החזירו את i.
אם לכל אינדקס נמצאה עותק, החזירו -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

סופרים אותיות, ואז סורקים

האינטואיציה

בפתרון בכוח גס שואלים שוב עבור כל מיקום: "האם האות הזו מופיעה במקום אחר?" במקום זאת, סופרים פעם אחת. קיימות רק 26 אותיות, ולכן מערך של 26 מונים מכיל את כל הספירות, עם אינדקס 0 עבור a ואינדקס 25 עבור z. האינדקס של אות הוא קוד התו שלה פחות הקוד של a.

המעבר הראשון ממלא את המונים. עבור coddycode הם מציגים: c: 2, o: 2, d: 3, y: 1, e: 1. המעבר השני עובר על המחרוזת משמאל ועוצר במיקום הראשון שבו הספירה של האות היא 1. זו האות y באינדקס 4. המעבר השני צריך לעבור על המחרוזת, ולא על 26 המונים, כי השאלה היא על המיקום הראשון, ולא על האות הראשונה באלפבית.

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

אלגוריתם

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

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

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

רוב הטעויות נובעות מהחלטה מוקדמת מדי או ממעבר על הדבר הלא נכון בסריקה השנייה.

בדיקה של האותיות שלפני המיקום i בלבד. ב-abca אין עותק של ה-a הראשונה לפניה, ובכל זאת היא אינה ייחודית.
מעבר על מערך המונים במקום על המחרוזת בסריקה השנייה. עבור ba, המונה הראשון ששווה ל-1 שייך ל-a, אבל התשובה היא האינדקס 0, של ה-b.
החזרת האות במקום האינדקס שלה, או החזרת האינדקס בספירה שמתחילה ב-1. ב-Lua וב-R הספירה מתחילה ב-1, לכן יש להפחית 1 לפני ההחזרה.
שכחת המקרה של -1. במחרוזת כמו aabbcc אין אות ייחודית, והפונקציה עדיין חייבת להחזיר ערך לאחר הלולאה.
שימוש בקוד התו הגולמי בתור אינדקס במערך המונים. הערך של a הוא 97, הרבה מעבר לסוף של מערך בן 26 איברים; יש להפחית תחילה את הקוד של a.

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

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

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

האם תוכל לפתור את זה במעבר אחד על המחרוזת?

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

האם כדאי להשתמש במפת גיבוב או במערך כדי לספור את האותיות?

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

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "coddycode"

צפוי