Subset / Subsequence String

Subset / subsequence string ialah salah satu topik yang sering keluar saat coding interview maupun competitive programming.

Seperti namanya, subset dari sebuah string merupakan himpunan bagian dari string. Sedangkan untuk pengertian secara general nya, subset ialah sebuah himpunan yang mana anggota himpunan tersebut merupakan anggota himpunan lain (superset).

Notasi matematika :
A ⊆ B

Yang berarti, himpunan A adalah himpunan bagian dari himpunan B

A = subset dari himpunan B
B = superset dari himpunan A

Lebih jelasnya, untuk string “AB”, subset nya ialah “A”, “B”, “AB” dan “”. Dimana “A”, “B”, “AB” dan “” juga merupakan member / elemen dari string “AB”.

Dalam teori himpunan, banyak subset dari sebuah himpunan ialah 2^n dengan n ialah kardinalitas atau banyaknya elemen dari himpunan tersebut.

Dengan melihat contoh subset dari string “AB” diatas, terlihat bahwa pola dari subset ialah dengan mengambil sebagian elemen atau mengambil semua elemen dan mengabaikan sebagian elemen lainnya.

Contohnya,

A = {1,2}
subset dari A ialah {{1}, {2}, {1, 2}, {2}}.

{1} merupakan subset dari A meskipun tidak ada angka 2 di {1}, karenanya bisa dikatakan subset ialah mengambil sebagian atau semuanya dan mengabaikan sebagian lainnya.

Konsep mengambil sebagian ataupun mengabaikan sebagian lainnya itu dapat diterapkan untuk rekursi. Perhatikan contoh dibawah.

Dalam mencari subset dari string “AB” kita dapat melakukannya dengan seperti ini :

Untuk tiap karakter di string “AB”, kita dapat mengambil karakter tersebut untuk diproses ataupun tidak

f(“”, “AB”) = f(“A”, “B”) + f(“”, “B”) + f(“B”, “A”) + f(“”, “A”)

Jika digambarkan recursion tree nya maka akan terlihat seperti berikut.

Bisa dilihat dibawah, pada node yang berada di dalam kotak, terlihat bahwa node tersebut menerapkan konsep mengambil sebagian dan mengabaikan sebagian, dalam kasus ini, node yang kiri mengabaikan semua karakter yang ada di “AB”, sedangkan node yang kanan hanya mengambil satu karakter dari string “AB” yaitu “A”.

Proses itu berulang-ulang, hingga tidak ada lagi karakter yang tersisa, sehingga ketika menemui kondisi dimana tidak ada karakter yang bisa diambil lagi, maka fungsi berhenti melakukan rekursi.

Dapat dilihat pada recursion tree diatas, pada node yang terdapat lingkaran berwarna biru, itu menandakan bahwa node tersebut telah menemui base case dimana tidak ada lagi karakter yang bisa diambil dari parameter ke-2 fungsi, sehingga nilai dari parameter pertama itulah yang merupakan subset.

Jika digabungkan, maka subset-subset itu ialah “”, “B”, “A”, “AB” yang merupakan elemen di string “AB”. Dengan ini kita sudah menyelesaikan masalah untuk mencari semua subset/subsequence dari sebuah string.

Sekarang, coba lihat bagaimana mengubah recursion tree yang telah kita buat menjadi kode.

Base case dari fungsi rekursif yang dibuat

Kode diatas merupakan base case dari permasalahan tersebut, dimana jika string nya kosong maka tidak ada lagi karakter yang bisa diambil untuk diproses.

Kode diatas adalah recursion case nya, dimana dapat dilihat terdapat 2 kali rekursi, rekursi pertama ialah dengan mengambil karakter pertama dari string, dan yang kedua mengabaikan karakter tersebut.

Kode lengkap untuk mencari semua subset dari sebuah string :

Perlu dicatat, saat pemanggilan fungsi, variable String processed selalu bernilai string kosong ( “” ).

Konsep subset/subsequence dengan menggunakan pendekatan mengambil sebagian atau mengabaikan sebagian ini banyak digunakan dalam rekursi, bahkan dalam tulisan pertama saya tentang permutasi juga menggunakan konsep ini.