Tingkat Kesulitan Hard
Kategori String, Data Structure
Pranala Soal Pranala Soal
Pranala Solusi Solusi 1 (Binary Search), Solusi 2 (Counting Sort)

Mengecek anagram

Sebelum kita menghitung banyaknya pasangan seperti yang diminta pada soal, kita harus bisa memeriksa apakah kedua string, misal $a$ dan $b$, adalah anagram satu sama lainnya.

Pertama, penjang keduanya harus sama. Tapi itu saja tidak cukup. Kita dapat menemukan bahwa kedua string bisa dikatakan anagram jika keduanya disusun dari huruf yang sama. Dengan kata lain, banyaknya a pada kedua string harus sama (mungkin 0 keduanya), banyaknya b juga harus sama, dst. Ada dua cara mengimplementasikan hal ini:

  1. Dengan menghitung banyak kemunculan tiap karakter, dan membandingkan keduanya, atau
  2. Dengan mengurutkan huruf-huruf pada kedua string.

Cara yang kedua lebih mudah untuk diimplementasikan.

Menghitung banyak pasangan anagram

Sekarang kita sudah tahu bagaimana mengecek apakah dua string anagram satu sama lainnya atau tidak. Berarti, kita bisa mengurutkan semua karakter pada masing-masing string, dan yang tersisa adalah mencari banyaknya pasangan string yang sama di kedua list.

Dengan kata lain, untuk setiap string pada $S$, kita harus mencari banyaknya string pada $T$ yang sama dengan string tersebut. Ada dua cara untuk melakukan ini:

  1. Dengan mengurutkan semua string pada $T$. Kemudian, untuk setiap string pada $S$, kita lakukan binary search pada $T$ untuk mencari tahu banyaknya string yang sama.
  2. Buat sebuah map yang menghitung banyaknya kemunculan string pada $T$. Pada sebagian besar bahasa pemrograman, tipe data map sudah siap untuk dipakai (contohnya std::map<std::string, int> pada C++, java.util.HashMap<String, int> pada Java, dan dict pada Python). Cara ini adalah cara yang paling mudah untuk diimplementasikan jika bahasa kalian sudah mempunyai tipe data map-nya sendiri.

Kompleksitas keduanya sama, yaitu $O((N+M) \log (M))$.