Hi!
For everyone dealing with this issue after messing with their python installation, I’ve managed to get apt to work smoothly again by reinstalling the package python3-commandnotfound:
sudo apt-get reinstall python3-commandnotfound
Hope this answer might help others!