First Unique Character in a String

+10

Kamu mendapatkan string s yang berisi huruf kecil bahasa Inggris. Temukan karakter pertama yang muncul tepat satu kali dalam seluruh string, lalu kembalikan indeksnya, dihitung dari 0. Jika setiap karakter muncul lebih dari satu kali, kembalikan -1.

Fungsi

firstUniqChar(s: string) → integer

sstring: string yang akan dicari, hanya huruf kecil
Mengembalikaninteger: indeks huruf pertama yang muncul tepat satu kali, atau -1 jika tidak ada

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf kecil bahasa Inggris (a hingga z).

Contoh

Input: s = "coddycode"
Output: 4
Penjelasan: Dalam coddycode, c dan o muncul dua kali, sedangkan d muncul tiga kali. y (indeks 4) dan e (indeks 8) masing-masing muncul satu kali, dan y muncul lebih dulu, jadi jawabannya adalah 4.

Input: s = "swiss"
Output: 1
Penjelasan: Huruf s muncul tiga kali. w pada indeks 1 dan i pada indeks 2 masing-masing muncul satu kali, dan w muncul lebih dulu.

Input: s = "aabbcc"
Output: -1
Penjelasan: Setiap huruf dalam aabbcc muncul dua kali, jadi jawabannya adalah -1.

Pertanyaan lanjutan

Karakter tiba satu per satu dari sebuah aliran. Bagaimana kamu melaporkan karakter pertama yang sejauh ini hanya muncul satu kali setelah setiap karakter tiba?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Sebuah huruf yang tampak unik saat kamu menemukannya bisa muncul lagi di bagian paling akhir string, jadi sekali melihat dari kiri ke kanan saja tidak cukup. Hitung setiap huruf terlebih dahulu, lalu lintasan kedua dapat menentukan dalam waktu konstan apakah setiap posisi berisi huruf yang unik.

Cari salinan kedua dari setiap huruf

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Untuk setiap posisi dari kiri, telusuri seluruh string untuk mencari posisi lain yang memiliki huruf yang sama. Periksa kedua sisi: salinan sebelumnya sama-sama membuat sebuah huruf tidak memenuhi syarat, begitu juga salinan setelahnya. Posisi pertama yang tidak memiliki salinan adalah jawabannya. Dalam coddycode, posisi 0 hingga 3 masing-masing memiliki salinan, sedangkan y pada indeks 4 tidak memilikinya.

Berhenti pada salinan pertama tidak membantu ketika setiap huruf berada dalam satu rangkaian panjang, seperti 2000 a, lalu 2000 b, dan seterusnya: setiap pemindaian melewati semua rangkaian sebelumnya. Saat n = 5 × 10^4, jumlahnya lebih dari satu miliar perbandingan.

Algoritma

Untuk setiap indeks i dari kiri ke kanan:
Periksa setiap indeks j selain i, lalu berhenti pada indeks pertama saat s[j] sama dengan s[i].
Jika tidak ada j seperti itu, kembalikan i.
Jika setiap indeks menemukan salinannya, kembalikan -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

Hitung huruf, lalu pindai

Intuisi

Hitung setiap huruf satu kali, alih-alih mencari lagi untuk setiap posisi. Hanya ada 26 huruf, jadi 26 penghitung dapat menyimpan semua jumlah, dengan indeks berupa kode huruf dikurangi kode a.

Lintasan pertama mengisi penghitung; untuk coddycode, hanya y dan e yang berakhir dengan nilai 1. Lintasan kedua menelusuri string dari kiri dan berhenti pada huruf pertama yang jumlahnya 1, yaitu y pada indeks 4. Dua lintasan dengan masing-masing n langkah membutuhkan waktu O(n), dan 26 penghitung membutuhkan ruang O(1) untuk panjang apa pun.

Algoritma

Buat array berisi 26 angka nol.
Untuk setiap huruf dalam s, tambahkan 1 ke penghitungnya.
Telusuri s lagi mulai dari indeks 0. Kembalikan indeks pertama yang hurufnya memiliki jumlah 1.
Jika penelusuran berakhir, kembalikan -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

Jebakan dan kasus tepi

Memeriksa hanya huruf sebelum posisi i. Dalam abca, a pertama tidak memiliki salinan sebelumnya, tetapi tetap tidak unik.
Menelusuri array penghitung, bukan string, pada lintasan kedua. Untuk ba, penghitung pertama yang bernilai 1 adalah milik a, tetapi jawabannya adalah indeks 0.
Mengindeks penghitung dengan kode karakter mentah. a bernilai 97, jauh melewati akhir 26 penghitung.
Mengembalikan huruf, bukan indeksnya, atau indeks berbasis 1 di Lua atau R.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Karakter Unik Pertama dalam String?

Menghitung huruf lalu memindai string memerlukan dua kali lintasan dengan n langkah, jadi waktunya adalah O(n). Ke-26 penghitung menggunakan ruang yang sama untuk panjang apa pun, jadi ruang tambahannya adalah O(1).

Bisakah kamu menyelesaikannya dengan satu kali melewati string?

Ya. Dalam satu kali pemindaian, simpan indeks kemunculan pertama setiap huruf, atau tandai sebagai berulang saat huruf itu muncul lagi. Lalu, ambil indeks terkecil di antara 26 huruf yang muncul satu kali. string dibaca sekali, dan pemeriksaan akhir membutuhkan 26 langkah.

Haruskah kamu menggunakan hash map atau array untuk menghitung huruf?

Jika hanya menggunakan huruf kecil, array dengan 26 penghitung berukuran lebih kecil dan lebih cepat. Hash map adalah pilihan yang tepat jika string dapat berisi karakter apa pun, seperti teks Unicode. Algoritmanya tetap sama: hitung, lalu telusuri string.

def firstUniqChar(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "coddycode"

Output yang diharapkan