CleanMyMac is particularly aggressive. It considers universal binaries “system junk” and offers to strip the part not appropriate for your current architecture, breaking apps in the process. For future reference, consider /System/Library/CoreServices/Applications/Storage Management.app as a more manual way of finding what’s eating up your disk space.
Didn’t you by any change setup Alfred’s Syncing? If so, even if your Workflows were deleted you might be able to recover them as some services (like Dropbox) allow you to restore deleted files.