I had installed CleanMyMac before, and have already uninstalled it.
However, I got the notification saying "It's time to clean your mac".
How is this possible and how can I avoid this?
The interesting thing about uninstalling CleanMyMac is that the best application for the job is, in fact CleanMyMac.
If you set it to uninstall itself, it will tidily clean up its own leftovers before finally quitting & trashing itself.
It is, in fact, probably quicker to re-install it, then get it to uninstall itself than to pick apart where the leftovers are.