I am in the midst of an excellent book, The Big Necessity, and the author does her best not to be too overtly in love with the state, but she does believe that creating more public toilets would solve all sorts of problems, such as long bathroom lines for women:

There would be fewer queues if there were more public bathrooms. All sorts of problems could be solved only if people in charge got it into their heads that providing their citizens with public toilets was not only the height of civility but good economic management.

…

settlements located on good roads can get an extra 20 carloads of people to stop every day, if they install a public necessity, which would mean as much revenue as a smallish factory. Restaurants and service stations know that decent bathrooms bring in trade, and outlandish toilets — ones that play language tapes, or have special glass that means you can see out, but that people cannot see in — bring the media, which brings clients. Effort is made in the private sector and nowhere else.

The incentives are just not there in the public sector to satisfy the needs of people – and when they are, there are few incentives (and not enough information) to get the needs satisfied properly. Despite this, and the above, folks still rely on government solutions first. Count me among the few (or many) people who are happy to know that the mall, McDonalds, convenience stores, etc. provide toilets and that New York State does not.