LeetCode Grinding
Algorithms3 menit baca

Solusi Leetcode - Remove All Adjacent Duplicates In String

Pakai stack untuk menghapus pasangan duplikat yang bersebelahan, termasuk pasangan baru yang muncul dari penghapusan sebelumnya.

Di artikel ini 8 bagian

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.

javascript
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

javascript
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

  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

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan