Changed permalink structure creating 404 page not found links

So i had a permalink structure like this:

Example #1: https://www.mysite.com/category1/some-wp-post
Example #2: https://www.mysite.com/category2/subcategory/some-wp-post

and now i changed it to:

https://www.mysite.com/some-wp-post

The problem is that the links from Example #2, do not redirect to the new url structure but they give 404 page not found instead. The links from Example #1 redirect just fine.

Any ideas why is that and how to correct it?