0Pricing
Coding Interview Prep · Pelajaran

Substring Terpanjang Tanpa Pengulangan

Melacak posisi terakhir yang terlihat dalam window

Substring Terpanjang Tanpa Pengulangan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Masalah Jendela Klasik

Temukan subteks terpanjang tanpa karakter berulang. Ini adalah contoh favorit jendela geser yang muncul di hampir setiap platform penilaian. 🔤

Jebakan Brute Force

Memeriksa duplikat pada setiap subteks membutuhkan sekitar O(n^2) atau lebih buruk. Untuk string panjang, cara itu terlalu lambat, sehingga diperlukan penelusuran yang lebih cerdas.

Jendela Karakter Berbeda

Pertahankan jendela yang selalu berisi karakter berbeda. Perluas dari kanan, dan ketika muncul pengulangan, kecilkan dari kiri sampai pengulangan tersebut hilang.

Ingat Posisi Terakhir

Simpan indeks terakhir setiap karakter dalam kamus. Dengan begitu, Anda dapat langsung mengetahui lokasi terakhir kemunculan pengulangan saat melakukan penelusuran.

last = {}
left = 0
best = 0

Telusuri Setiap Karakter

Lakukan perulangan dengan kanan pada string, sambil membaca indeks dan karakter pada setiap langkah. Hal ini menggerakkan jendela maju satu posisi setiap kali.

for right, ch in enumerate(s):

Lompati Penunjuk Kiri

Jika karakter tersebut terlihat di dalam jendela saat ini, pindahkan kiri tepat ke posisi setelah kemunculan terakhirnya. Dengan satu langkah, karakter duplikat pun dihapus dari jendela.

    if ch in last and last[ch] >= left:
        left = last[ch] + 1

Perbarui dan Ukur

Catat posisi baru karakter ini, lalu jendela dari kiri hingga kanan tidak lagi memiliki duplikat. Panjangnya adalah kanan dikurangi kiri ditambah satu.

    last[ch] = right
    best = max(best, right - left + 1)

Mengapa Pemeriksaan Ini Penting

Pemeriksaan last[ch] >= left sangat penting. Tanpanya, posisi lama yang berada di luar jendela akan keliru menggeser kiri ke belakang.

Waktu Linear, Ruang Linear

Setiap karakter dikunjungi satu kali dan kiri hanya bergerak maju, sehingga penelusurannya adalah O(n). Kamus menggunakan ruang untuk menyimpan karakter-karakter yang berbeda.

Tangani Kasus Tepi

String kosong menghasilkan nol, sedangkan string yang berisi satu huruf berulang menghasilkan satu. Periksa keduanya sebelum mengirimkan jawaban agar terhindar dari WA yang mengecoh.

Pola yang Dapat Digunakan Ulang

Peta kemunculan terakhir ditambah penunjuk kiri yang melompat dapat diterapkan pada banyak masalah keberbedaan, seperti jendela dengan paling banyak satu pengulangan.

Pemeriksaan Cepat

Anda melacak indeks terakhir setiap karakter saat mencari subteks unik terpanjang.

Ringkasan

Geser jendela berisi karakter unik, simpan setiap posisi terakhir, lalu lompati pengulangan dengan menggeser kiri. Cara ini menyelesaikan masalah klasik tersebut dalam O(n). ✅

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Substring Terpanjang Tanpa Pengulangan” gratis?

Ya — teks lengkap “Substring Terpanjang Tanpa Pengulangan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Substring Terpanjang Tanpa Pengulangan”?

Melacak posisi terakhir yang terlihat dalam window Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Substring Terpanjang Tanpa Pengulangan” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Jumlah Window Berukuran Tetap
  2. Window Variabel dengan Two Pointer
  3. Substring Terpanjang Tanpa Pengulangan
  4. Menghitung Window yang Memenuhi Aturan
← Kembali ke Coding Interview Prep