Solusi Leetcode - Valid Palindrome

Palindrome adalah teks yang dibaca sama dari depan maupun dari belakang. Insting pertama saya adalah membalik string-nya lalu membandingkan, tapi cara itu membuat string baru dan memakai extra space O(n). Ada cara yang lebih baik dengan space O(1): teknik two pointers.

Algoritmanya bisa langsung membandingkan karakter di kedua ujung yang berseberangan. Lalu bergerak ke tengah sampai ketemu karakter yang nggak cocok atau kedua pointer bertemu.

Memahami Soalnya

LeetCode 125 memakai input berupa karakter ASCII yang printable. Abaikan tanda baca dan spasi, lalu bandingkan huruf tanpa membedakan huruf besar dan kecil. Digit tetap ikut dibandingkan. Contohnya, "A man, a plan, a canal: Panama" valid, sedangkan "race a car" nggak.

Pendekatan Pertama Saya

Versi pertama menghapus karakter yang bukan alfanumerik dan mengubah huruf jadi lowercase. Setelah itu hasilnya dibalik, lalu kedua string dibandingkan:

function isPalindromeNaive(s) {
  const normalized = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  const reversed = normalized.split("").reverse().join("");
  return normalized === reversed;
}

String yang dinormalisasi dan string yang dibalik memakai extra space O(n). Versi two pointer langsung mengecek input aslinya.

Insight dari Two Pointers

Pendekatan two pointer mengecek kedua ujung sekaligus, lalu bergerak ke tengah sampai menemukan karakter yang nggak cocok atau memastikan kalau string-nya palindrome.

Teknik two pointers cocok di sini karena palindrome itu simetris. Kalau karakter di kedua ujung cocok, saya bisa bergerak ke tengah dan mengecek pasangan berikutnya. Kalau nggak cocok, saya tahu itu bukan palindrome.

Implementasi two pointer

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    // Skip characters that the problem excludes from comparison.
    while (left < right && !/[a-z0-9]/i.test(s[left])) left++;
    while (left < right && !/[a-z0-9]/i.test(s[right])) right--;
    if (left >= right) break;

    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }

    // Move both pointers inward
    left++;
    right--;
  }

  return true; // All characters matched!
}

Trace pointer

Untuk "racecar", pointer-nya bergerak seperti ini:

• Awal: left=0 ('r'), right=6 ('r')
• Karakternya cocok, jadi bergerak ke tengah: left=1, right=5
• left=1 ('a'), right=5 ('a'): cocok! Bergerak ke tengah: left=2, right=4
• left=2 ('c'), right=4 ('c'): cocok! Bergerak ke tengah: left=3, right=3
• left >= right, keluar dari loop
• Return true!

Kenapa Pendekatan Ini Lebih Baik

Space Complexity: O(1)

• Nggak ada salinan input yang dinormalisasi secara utuh
• Cuma pakai dua variabel integer untuk pointer

Time Complexity: O(n)

• Satu pass di sepanjang string
• Tiap pointer bergerak ke satu arah, jadi total kerjanya O(n)
• Berpotensi lebih cepat daripada membalik string karena kita bisa berhenti lebih awal kalau ketemu karakter yang nggak cocok

Kesederhanaan

• Logikanya lugas dan gampang dipahami
• Nggak butuh operasi string yang rumit

Kesalahan yang Sering Terjadi

Waktu mengimplementasikan ini, hati-hati dengan:

1. Off by one error: Pastikan kondisi loop kamu left < right (bukan <=) supaya karakter tengah nggak dicek dua kali
2. Edge case: String kosong dan string satu karakter itu palindrome menurut definisinya
3. Aturan input: Abaikan tanda baca dan spasi. Bandingkan huruf tanpa membedakan huruf besar dan kecil, dan tetap sertakan digit.

Ringkasan palindrome

• Two pointers dari kedua ujung pas banget untuk soal yang simetris kayak palindrome
• Nggak perlu membalik string kalau kamu bisa mengecek langsung
• Waktu O(n), space O(1). Ini optimal untuk soal ini
• Pattern ini muncul di banyak soal string dan array

Teknik two pointers berguna untuk soal yang melibatkan simetri atau hubungan antara kedua ujung yang berseberangan dari sebuah sequence.