Solusi Leetcode - Palindrome Permutation

Buat ngecek apakah sebuah string bisa disusun ulang jadi palindrome, kita nggak perlu bikin semua permutasinya. Yang menentukan adalah frekuensi tiap karakter: paling banyak cuma boleh ada satu karakter yang jumlahnya ganjil.

Syarat sebuah palindrome

Diberikan sebuah string, tugasnya adalah menentukan apakah ada permutasi yang dibaca sama dari depan maupun dari belakang, misalnya "racecar" atau "aabbaa". Karakter yang nggak ada di tengah harus punya pasangan, jadi setiap jumlah karakter harus genap, kecuali mungkin satu jumlah untuk palindrome yang panjangnya ganjil.

Baseline dengan membuat permutasi

Pikiran awal saya adalah membuat semua permutasi lalu mengecek satu per satu. Pseudocode ini mengasumsikan ada helper generatePermutations dan isPalindrome:

function canPermuteToPalindromeNaive(str) {
  // Generate all permutations (this is O(n!) - terrible!)
  const permutations = generatePermutations(str);

  for (let perm of permutations) {
    if (isPalindrome(perm)) {
      return true;
    }
  }
  return false;
}

Membuat permutasi butuh O(n! × n), yang dengan cepat jadi nggak praktis. Untuk string dengan panjang 10, cara ini bakal memeriksa lebih dari 3,6 juta permutasi.

Syarat frekuensi dan implementasinya

Untuk string yang panjangnya genap, jumlah setiap karakter harus genap. Untuk string yang panjangnya ganjil, satu jumlah ganjil bisa menempati posisi tengah dan semua jumlah lainnya harus genap. Jadi algoritmanya menghitung frekuensi yang ganjil, bukan menyusun permutasi.

function canPermuteToPalindrome(str) {
  const frequencies = {};

  // Count frequency of each character
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    frequencies[char] = (frequencies[char] || 0) + 1;
  }

  // Count how many characters appear odd times
  let oddCount = 0;
  for (let char in frequencies) {
    if (frequencies[char] % 2 === 1) {
      oddCount++;
    }
  }

  // Can form palindrome if at most 1 character appears odd times
  return oddCount <= 1;
}

Contoh, kompleksitas, dan detail input

Jumlah yang genap bisa dibagi ke dua sisi palindrome. Satu karakter sisa bisa duduk di tengah kalau panjang string-nya ganjil. Lebih dari satu jumlah ganjil berarti ada minimal satu karakter yang nggak punya pasangan.

Aturan frekuensi ini memberikan hasil berikut:

Untuk "aab":

• Frekuensi: a=2, b=1
• Jumlah frekuensi ganjil: 1 (cuma 'b')
• Hasil: true (bisa jadi "aba")

Untuk "code":

• Frekuensi: c=1, o=1, d=1, e=1
• Jumlah frekuensi ganjil: 4 (semua karakter)
• Hasil: false (nggak bisa membentuk palindrome)

Untuk "aabb":

• Frekuensi: a=2, b=2
• Jumlah frekuensi ganjil: 0
• Hasil: true (bisa jadi "abba")

Untuk "carerac":

• Frekuensi: c=2, a=2, r=2, e=1
• Jumlah frekuensi ganjil: 1 (cuma 'e')
• Hasil: true (bisa jadi "racecar")

Implementasi pertama memindai string sekali, lalu memindai map frekuensinya. Dengan k karakter unik, time complexity-nya O(n + k), yang sama dengan O(n) karena k ≤ n. Map-nya pakai space O(k).

Implementasi ini menganggap huruf besar dan huruf kecil sebagai nilai yang berbeda. Whitespace dan karakter spesial juga ikut dihitung. String kosong nggak punya frekuensi ganjil, jadi implementasinya mengembalikan true. Contoh-contoh ini pakai string ASCII. Untuk teks Unicode, kedua versi butuh definisi karakter yang sama.

Update dalam satu pass dan pelajarannya

Saya bisa menghindari scan kedua atas map dengan meng-update jumlah frekuensi ganjil setiap kali frekuensi sebuah karakter berubah paritas:

function canPermuteToPalindrome(str) {
  const frequencies = {};
  let oddCount = 0;

  for (let char of str) {
    frequencies[char] = (frequencies[char] || 0) + 1;
    
    // Update odd count on the fly
    if (frequencies[char] % 2 === 1) {
      oddCount++;
    } else {
      oddCount--;
    }
  }

  return oddCount <= 1;
}

Versi ini tetap berjalan dalam O(n) time dan O(k) space, tapi state jumlah frekuensi ganjilnya dijaga selama scan pertama.

Saya senang waktu sadar kalau sifat palindrome bikin kita nggak perlu lagi membuat permutasi. Menghitung state yang penting adalah cara umum untuk mengubah exhaustive search jadi linear scan.