Can't do additional updates using sudo apt update error : Problem executing scripts

I am using Ubuntu v20.04.5 LTS for Windows 11. While trying to run sudo apt update. I get the following error

Hit:5 http://archive.ubuntu.com/ubuntu focal-backports InRelease
Fetched 114 kB in 2s (58.3 kB/s)
Traceback (most recent call last):
  File "/usr/lib/cnf-update-db", line 8, in <module>
    from CommandNotFound.db.creator import DbCreator
  File "/usr/lib/python3/dist-packages/CommandNotFound/db/creator.py", line 12, in <module>
    import apt_pkg
ModuleNotFoundError: No module named 'apt_pkg'
Reading package lists... Done
E: Problem executing scripts APT::Update::Post-Invoke-Success 'if /usr/bin/test -w /var/lib/command-not-found/ -a -e /usr/lib/cnf-update-db; then /usr/lib/cnf-update-db > /dev/null; fi'
E: Sub-process returned an error code.

I've tried re-installing python 3

sudo apt-get install python3-apt --reinstall

Then created a symlink from apt_pkg 34m to apt_pkg 35m & apt_pkg35m to apt_pkg36m

cd /usr/lib/python3/dist-packages
sudo ln -s apt_pkg.cpython-{34m,35m}-x86_64-linux-gnu.so apt_pkg.so
sudo ln -s apt_pkg.cpython-{35m,36m}-x86_64-linux-gnu.so apt_pkg.so

I'm not quite sure executing the above commands helped out on anything. Or I am totally off the track in solving this one. I don't seem to understand why this is happening. Does anyone who might have a rough idea of where the problem is?