I had much the same experience in Stockholm.
In Sweden, the rental market is staggeringly State-controlled. It is actually illegal to rent without permission from the State. The way it works is that as time passes, you build up points, and the more points you have, the nicer the apartments you're allowed to rent. It takes over twenty years to legally rent in central Stockholm. The State (of course) sets the rent price, and it is very, very low. You then have a secondary market, where tenants can sublet, without the knowledge or consent of the owner, and they mark up the rent to the market price. AirBnB helped enormously until it was basically banned.
It's hell for everyone, in the name of being fair, which it absolutely is not, and of course the ultimate effect is to profoundly discourage the construction of new properties, so there's *also* a crippling shortage of properties, too.
Given all this, when companies want to hire people from outside Sweden, they have to provide housing for them, because it's impossible to legally rent in Stockholm, and a nightmare to illegally rent (and no one coming in from the outside can cope with that market).
What that means is the company turns to private companies which hold their own stock of property and you pick one and pay the rent - and so when you leave or lose your job, you also lose your apartment.
The best place to rent, IME, has always been London. I'm sure plenty of people think it's bad there, but it can be and is, in so many European cities, *profoundly* worse.