Algorithm for purely categorical data
K-medoids of course works for purely categorical data.

But there also is k-modes, easy to find with a little bit of research... It's much cheaper to run, it is O(n), not O(n²)

It doesn't solve the problem that categorical data usually will not cluster in a meaningful way...