Longest Substring Without Repeating Characters
Kamu mendapatkan sebuah string s. Temukan substring terpanjang, yaitu rangkaian karakter yang bersebelahan, yang tidak memiliki karakter berulang, lalu kembalikan panjangnya.
Huruf besar dan huruf kecil dihitung sebagai karakter yang berbeda, jadi a dan A bukan karakter yang berulang.
Fungsi
- sstring
- string yang dicari
- Mengembalikaninteger
- panjang substring terpanjang tanpa karakter berulang
Batasan
1 ≤ s.length ≤ 5 × 104shanya berisi huruf bahasa Inggris (huruf kecil dan huruf besar) dan angka.- Huruf besar dan huruf kecil adalah karakter yang berbeda.
Contoh
- Input
- s = "coddycode"
- Output
- 5
- Penjelasan
ycodeberisi lima karakter yang berbeda. Menambahkanddi depannya menghasilkandycode, dengandsebanyak dua kali, dan tidak ada rangkaian lain yang terdiri dari lima karakter atau lebih tanpa pengulangan.
- Input
- s = "racecar"
- Output
- 4
- Penjelasan
racedanecarsama-sama memiliki empat huruf yang berbeda. Setiap rangkaian lima huruf berisi satu huruf yang sama sebanyak dua kali.
- Input
- s = "a1b2a3b"
- Output
- 5
- Penjelasan
- Digit juga dihitung sebagai karakter, jadi
1b2a3memiliki lima karakter berbeda. Kedua rangkaian yang terdiri dari enam karakter masing-masing memilikiakedua ataubkedua.
Pertanyaan lanjutan
Apa yang akan kamu ubah jika s dapat menyimpan karakter Unicode apa pun, bukan hanya huruf dan angka?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Substring adalah bagian string yang berurutan, jadi kamu mencari rentang terpanjang yang bisa kamu ambil tanpa menemukan karakter yang sama dua kali.
Pertahankan jendela dengan tepi kiri dan tepi kanan. Perbesar jendela dari sisi kanan satu karakter setiap kali, lalu pindahkan tepi kiri hanya jika karakter baru sudah berada di dalam jendela.
Simpan indeks terakhir tempat setiap karakter muncul. Jika karakter baru terakhir terlihat pada atau setelah tepi kiri, pindahkan tepi kiri ke satu posisi setelah indeks tersebut. Tepi kiri tidak pernah bergerak mundur, dan jawabannya adalah jendela terlebar yang pernah kamu miliki.
Solusi
Pertahankan sebuah jendela: dua batas yang mengapit rangkaian tanpa karakter berulang. Batas kanan membaca setiap karakter satu kali dan batas kiri hanya bergerak maju, sehingga satu kali pemindaian menemukan, untuk setiap posisi akhir, rangkaian terpanjang tanpa pengulangan yang berakhir di sana.
Periksa setiap substring
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Coba setiap posisi awal dan akhir, lalu uji setiap substring dengan menambahkan karakternya ke dalam set sampai ada karakter yang sudah ada di sana. Setiap kandidat diuji, jadi substring valid terpanjang tidak mungkin terlewat.
Ada sekitar n²/2 substring, yaitu 1.25 × 10^9 untuk n = 5 × 10^4, dan satu pengujian dapat membaca hingga n karakter: O(n³). Di sini, satu pengujian berhenti setelah paling banyak 63 karakter, karena string hanya memiliki 62 karakter yang berbeda, tetapi masih ada lebih dari satu miliar pengujian.
Algoritma
- Tetapkan
bestke 0. - Untuk setiap indeks awal, lakukan perulangan pada setiap indeks akhir dari indeks awal hingga akhir string.
- Tambahkan karakter substring satu per satu ke set kosong, lalu berhenti pada karakter pertama yang sudah ada di dalam set.
- Jika tidak ada karakter yang berulang dan panjang substring melebihi
best, simpan panjangnya. - Kembalikan
best.
def lengthOfLongestSubstring(s):
def has_no_repeat(start, end):
seen = set()
for k in range(start, end + 1):
if s[k] in seen:
return False
seen.add(s[k])
return True
best = 0
n = len(s)
for start in range(n):
for end in range(start, n):
if has_no_repeat(start, end):
best = max(best, end - start + 1)
return best
Sliding window dengan set
Intuisi
Jika abc tidak memiliki karakter berulang, untuk menguji abcd cukup ajukan satu pertanyaan: apakah d ada di antara a, b, dan c? Set karakter dalam jendela menjawabnya sekaligus.
Geser right satu langkah setiap kali. Jika karakter baru ada di dalam set, hapus karakter dari kiri sampai salinannya yang lebih awal hilang, lalu tambahkan karakter itu dan ukur. Kamu hanya membuang karakter jika memang perlu, jadi untuk setiap right, jendela tersebut adalah rangkaian terpanjang tanpa pengulangan yang berakhir di sana, dan substring terbaik berakhir di suatu tempat. Setiap karakter masuk ke set sekali dan keluar paling banyak sekali: O(n).
Algoritma
- Mulai dengan set kosong,
left = 0danbest = 0. - Pindahkan
rightke setiap indeks. - Selama
s[right]ada di dalam set, hapuss[left]dan majukanleftsatu langkah. - Tambahkan
s[right]ke dalam set. - Jika
right - left + 1lebih besar daribest, simpan nilai tersebut. - Kembalikan
best.
def lengthOfLongestSubstring(s):
in_window = set() # the characters between left and right
left = 0
best = 0
for right in range(len(s)):
# Shrink from the left until s[right] is no longer inside.
while s[right] in in_window:
in_window.remove(s[left])
left += 1
in_window.add(s[right])
best = max(best, right - left + 1)
return best
Jendela geser yang melompat ke indeks kemunculan terakhir
Intuisi
Kamu sudah tahu ke mana left harus berpindah: satu posisi setelah salinan sebelumnya dari karakter baru. Simpan indeks terakhir setiap karakter dalam map atau array dengan satu slot untuk setiap kode karakter, lalu left berpindah ke sana dalam satu langkah.
Lakukan perpindahan hanya jika indeks tersebut berada di posisi left atau setelahnya. Salinan yang lebih lama sudah berada di luar jendela, dan berpindah ke sana akan menggeser left ke belakang. Jendela pada setiap langkah sama dengan yang dibuat versi set, dan kini setiap karakter hanya membutuhkan satu pencarian, satu perbandingan, dan satu penulisan.
Algoritma
- Buat map kosong dari karakter ke indeks terakhir, lalu atur
left = 0danbest = 0. - Gerakkan
rightmelewati setiap indeks, lalu baca karakterchdi sana. - Jika
chterakhir terlihat pada indeks yang sama dengan atau setelahleft, aturleftke indeks tersebut ditambah satu. - Catat
rightsebagai indeks terakhirch. - Jika
right - left + 1lebih besar daripadabest, simpan nilai tersebut. - Kembalikan
best.
def lengthOfLongestSubstring(s):
last_seen = {}
start = 0
best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = i
if i - start + 1 > best:
best = i - start + 1
return best
Jebakan dan kasus tepi
- Menggeser
leftke belakang. Dalamabba,ayang lebih awal pada indeks 0 sudah berada di luar jendela saat kamu mencapaiaterakhir. Melompat ke indeks 1 membawabkedua kembali ke dalam jendela dan menghasilkan 3, bukan 2. - Menghitung jendela sebagai
right - left. Kedua ujungnya berada di dalam jendela, jadi tambahkan satu. - Mengubah string menjadi huruf kecil terlebih dahulu.
adanAadalah karakter yang berbeda di sini, jadi panjangaAadalah 2. - Mengukur hanya saat karakter berulang muncul. String tanpa karakter berulang, seperti
z, tidak pernah memicunya, sehingga hasilnya 0.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu dari Substring Terpanjang Tanpa Karakter Berulang?
Sliding window berjalan dalam waktu O(n), dengan n sebagai panjang string: sisi kanan membaca setiap karakter satu kali dan sisi kiri hanya bergerak maju. Ruang tambahan adalah O(k), dengan k sebagai jumlah karakter berbeda yang dapat dimuat string, yaitu 62 di sini.
Sebaiknya kamu menggunakan hash map atau array untuk indeks terakhir?
Keduanya membutuhkan waktu O(n). Dengan sekumpulan karakter tetap yang kecil, seperti di sini, array yang diindeks berdasarkan kode karakter menghindari hashing dan lebih cepat.
Apa perbedaan antara substring dan subsequence?
Substring adalah blok karakter yang bersebelahan, seperti ode dalam coddycode. Subsekuens dapat melewati karakter, seperti cdy. Soal ini meminta substring, karena itu window dengan dua tepi dapat digunakan.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def lengthOfLongestSubstring(s):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
s = "coddycode"
Output yang diharapkan
5