Around here a different solution has been in force for about a decade - remove all public toilets

(as well as seats, park benches, bus shelters etc.)
So - air freshners, just get a box of plastic gloves, a few hundred masks, and keep stealing them until they give up putting them in there, or you end up somewhere with none
edit - to increase the specificity of my reply.
My local sainsburys used to have toilets near the main entrance, to the left of and behind the customer service desk, with signs, all over the place pointing to them.
Then, several years ago they did a remodel. I have absolutely no idea where they are now, no signs, nowhere in the main entrance, checkout area, or shop anyway. I assume, upon reflection, that they probably exist somewhere, but.....