I knew people who moved from Stockholm to Berlin and kept on paying their rent in Stockholm, just so they don't lose their apartment. That's how hard it is to get one.
Berlin also had a rent cap, so instead of competing on price, you had to compete on intangibles like: letters of recommendation from previous landlords, proof of income and good conduct, having a high-profile job, nationality, etc.
Since supply is low, demand is sky-high and prices are capped, you had 30-40 people applying for the same apartment. Add the fact that once a landlord takes you in, there is almost no way that they can kick you out and you will end up with a very complicated and long vetting process that doesn't exactly favor the working class folks.
Also, you can end up with other costly requirements like: the landlord will only choose a tenant who buys all the furniture in the house. That's one example of an unregulated cost increase that is not affected by the rent cap.