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 מופיעה שלוש פעמים. גם y (אינדקס 4) וגם e (אינדקס 8) מופיעות פעם אחת, ומכיוון ש־y מופיעה ראשונה, התשובה היא 4.

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

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

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

האינטואיציה

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

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

המעבר הראשון ממלא את המונים; עבור coddycode, רק y ו-e מסתיימות בספירה 1. המעבר השני עובר על המחרוזת משמאל ועוצר באות הראשונה שהספירה שלה היא 1, האות y באינדקס 4. שני מעברים של n צעדים נותנים זמן 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.
שימוש בקוד התו הגולמי כאינדקס למונים. הערך של a הוא 97, הרבה מעבר לסוף מערך המונים שמכיל 26 איברים.
החזרת האות במקום האינדקס שלה, או החזרת אינדקס שמתחיל ב-1 ב-Lua או ב-R.

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

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

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

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

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

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

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

s = "coddycode"

הפלט הצפוי