Solusi Leetcode - Remove All Adjacent Duplicates In String

Menghapus karakter duplikat yang bersebelahan bisa memunculkan pasangan baru yang juga harus dihapus. Contohnya, "abbaca" jadi "aaca" setelah "bb" dihapus, lalu jadi "ca" setelah "aa" dihapus. Solusi pertama saya terus melakukan iterasi sampai nggak ada lagi duplikat yang ketemu, tapi stack bisa menangani penghapusan beruntun ini dalam satu pass.

Stack mendukung perilaku "hapus lalu cek lagi" ini. Waktu kita ketemu karakter yang sama dengan top dari stack, kita pop karakter itu (menghapus duplikatnya). Kalau nggak, kita push. Cara ini otomatis menangani penghapusan beruntun dalam satu pass.

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"

Tantangannya adalah melakukan ini secara efisien. Pendekatan naive mungkin butuh beberapa kali pass, tapi kita bisa menyelesaikannya dalam satu pass dengan data structure yang tepat.

Pendekatan Pertama Saya

Solusi awal saya terus melakukan scan dan menghapus duplikat sampai nggak ada lagi yang ketemu.

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.

Insight dari Stack

Stack cocok untuk soal ini karena sifat LIFO (Last In, First Out)-nya menangani perilaku "hapus lalu cek lagi":

• 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

Stack secara alami menangani perilaku penghapusan beruntun:

• Sifat LIFO: Karakter terakhir yang ditambahkan adalah karakter pertama yang kita bandingkan
• Cascading otomatis: Waktu kita pop sebuah duplikat, top yang baru mungkin sama dengan karakter berikutnya
• Single pass: Kita memproses setiap karakter tepat satu kali
• Efisien: Waktu O(n) dan space O(n) di worst case

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

Waktu mengimplementasikan ini, hati-hati dengan:

1. Cek stack kosong: Selalu cek apakah stack kosong sebelum mengakses top-nya
2. Index vs value: Pastikan kamu membandingkan karakter, bukan index
3. Menggabungkan hasil: Jangan lupa join array stack-nya di akhir
4. Edge case: String kosong harus mengembalikan string kosong

Apa yang diberikan stack

• Stack menangani pasangan yang cocok dan penghapusannya lewat semantik LIFO
• Satu pass cukup untuk menangani penghapusan beruntun
• Pattern yang sama berlaku untuk mencocokkan bracket dan soal string sejenis

Solusi stack ini lebih bersih daripada percobaan pertama saya. Memilih data structure yang tepat bikin algoritmanya lebih sederhana dan juga membantu di soal lain yang berurusan dengan pencocokan atau penghapusan beruntun.