Menghapus "bb" dari "abbaca" menyisakan "aaca", sehingga muncul pasangan lain yang perlu dihapus. Stack menangani keduanya dalam scan yang sama dengan menyimpan karakter yang masih tersisa.
Memahami Soalnya
Diberikan sebuah string, hapus pasangan karakter duplikat yang bersebelahan berulang kali sampai nggak ada duplikat lagi. Contohnya:
- "abbaca" → hapus "bb" → "aaca" → hapus "aa" → "ca"
Scan berulang
Versi ini menelusuri string lagi setiap kali sebuah pass menghapus setidaknya satu pasangan.
function removeDuplicatesNaive(str) {
let result = str;
let found = true;
while (found) {
found = false;
let temp = "";
for (let i = 0; i < result.length; i++) {
if (i < result.length - 1 && result[i] === result[i + 1]) {
i++; // Skip both characters
found = true;
} else {
temp += result[i];
}
}
result = temp;
}
return result;
}
Scan yang berulang ini butuh waktu O(n²) di worst case. Satu pass men-scan sisa karakter, dan beberapa input butuh n/2 pass penghapusan. Input "aaaa" bukan kasus seperti itu: pass pertama langsung menghapus kedua pasangannya.
Menyimpan karakter yang tersisa di stack
Bandingkan setiap karakter baru dengan karakter terakhir yang masih ada di stack:
- Waktu kita ketemu sebuah karakter, kalau karakter itu sama dengan top dari stack, kita pop (menghapus duplikatnya)
- Kalau nggak, kita push karakter itu
- Waktu kita pop sebuah duplikat, top yang baru mungkin sama dengan karakter berikutnya, jadi penghapusan beruntun otomatis tertangani
Algoritmanya membaca setiap karakter input satu kali.
Implementasi stack
function removeDuplicates(str) {
const stack = [];
for (let char of str) {
// If stack is not empty and top matches current char, pop (remove duplicate)
if (stack.length > 0 && stack[stack.length - 1] === char) {
stack.pop();
} else {
// Otherwise, push the character
stack.push(char);
}
}
// Join remaining characters
return stack.join("");
}
Trace stack
Untuk "abbaca", isi stack berubah seperti ini:
- Proses 'a': stack kosong, push 'a' → stack = ['a']
- Proses 'b': top-nya 'a' (beda), push 'b' → stack = ['a', 'b']
- Proses 'b': top-nya 'b' (sama!), pop → stack = ['a']
- Proses 'a': top-nya 'a' (sama!), pop → stack = []
- Proses 'c': stack kosong, push 'c' → stack = ['c']
- Proses 'a': top-nya 'c' (beda), push 'a' → stack = ['c', 'a']
Hasil: "ca"
Penghapusan duplikat membatalkan penambahan sebelumnya ke stack. Top yang baru bisa sama dengan karakter input berikutnya. Perbandingan inilah yang menangani penghapusan lanjutan dalam scan yang sama.
Kenapa Ini Berhasil
Setelah setiap karakter input diproses, stack berisi awalan string yang semua pasangan bersebelahannya udah dihapus. Karakter baru cuma bisa membentuk pasangan di puncak stack.
Analisis Complexity
Time Complexity: O(n)
- Satu pass di sepanjang string
- Setiap karakter diproses tepat satu kali
- Operasi stack (push/pop) itu O(1)
Space Complexity: O(n)
- Di worst case, kita mungkin menyimpan semua karakter di stack (misalnya "abc" yang nggak punya duplikat)
- Tapi cara ini menghindari pembuatan banyak string perantara
Kesalahan yang Sering Terjadi
- Cek stack kosong: Selalu cek apakah stack kosong sebelum mengakses top-nya
- Index vs value: Pastikan kamu membandingkan karakter, bukan index
- Menggabungkan hasil: Jangan lupa join array stack-nya di akhir
- Edge case: String kosong harus mengembalikan string kosong

Memuat komentar...