b belajar.myudak
☰ Daftar soalRoadmap‹›

Longest Common Subsequence

sedangDP 2 DimensiAnalisis dan Strategi Algoritma

Kembalikan panjang subsequence bersama terpanjang dari dua string. Subsequence dibentuk dengan menghapus nol atau lebih karakter tanpa mengubah urutan sisanya.

"abcde", "ace" → 3   // "ace"
"abc",   "def" → 0

LCS adalah dasar dari diff (membandingkan file) dan perbandingan sekuens DNA di Bioinformatika.

Topik
dynamic programmingstring
Petunjuk 1

Bandingkan karakter terakhir kedua string. Jika sama, ia pasti bagian dari LCS.

Petunjuk 2

Jika berbeda, buang karakter terakhir salah satu string dan ambil yang terbaik: max(dp[i−1][j], dp[i][j−1]).

Pengaturan editor

Ukuran font
Ukuran huruf di editor.
Ukuran tab
Lebar indentasi. Otomatis: 2 spasi untuk TypeScript, 4 untuk Python.
Key bindings
Ganti ke mode Vim.
Nomor baris relatif
Nomor baris dihitung dari posisi kursor (berguna untuk gerakan Vim).
Word wrap
Baris panjang dilipat agar muat di lebar editor.
IntelliSense
Saran kode otomatis saat mengetik (Ctrl+Spasi tetap bisa dipakai saat mati).

Nilai ditulis sebagai JSON. Output yang diharapkan dihitung dari solusi referensi.