Declaring what the type of 'maze' is would be nice. Also, I see most (if not all) solutions split the string into lines by '\n'. A list of lists (or at least list of strings) is easier to work with and makes much more sense in a task like this.

The idea is that no number from the interval (n/2, n) will ever be a divisor of n.

You are almost correct, however, we need to be careful about how we simplify the equations. The time complexity of making a single slice is (omikron) O(n). Making two of them, theoretically has a time complexity of O(n + n = 2n). Note that we are adding, not multiplying. Since 2 is a constant, we can omit counting it. (In other words, the functions n and 2n grow at the same rate.) Just making the slices has therefore a time complexity of O(n).

This happens for every element, so we then multiply by n and get O(n²).

Yes. The "else: pass" in your code can be omitted without any issues.

I'm not sure if I understood you correctly, but this is, in fact, O(n^2) too.

While one-liners look smart and cool, this is not really good practice. For every element of the list we make a slice (so in worst case, we go over all of its elements again) and then call the count method on the slice (by which we go over all of the elements of the slice).
In the end, what could be done with just one iteration over the list, is done with numerous redundant iterations.

Also, looking up if an element is in a set happens in a constant time, i. e., it always takes the same amount of time, regardless of the size of the set. Looking up if an element is in a list happens in a linear time, i. e. in the worst case, it has to go over all the elements of the list, and here, it would be very inefficient since we have to search the data structures repeatedly.

In one line but for what price... The code is terribly inefficient. Your solution has more lines but it is faster and cleaner.

Absolutely not best practice. Number of instances of one character is something you can very easily do with just one iteration over the string. This code goes over the entire string for each character unnecessarily.
I really wish newbies shifted their efforts from making "fancy" one-liners with terrible efficiency to writing actual respectable pieces of code. And I also wish people stopped upvoting codes like these as "Clever" or even "Best Practices".

It's a possibility and a smart one, but absolutely not "Best practice". In the worst case, the slice has to go over all the elements of the array and since it happens in a loop, the function ends up being quadratic (= time needed for its execution is proportional to len(arr)^2). However, this could be solved with linear complexity (= time needed for the execution is proportional to just len(arr)).