They should include in the description:
"brackets must be closed in the order they were opened"
Otherwise, test case #4 " "[(])" => False" is valid

Not a kata issue! Your code should be checking for such conditions beforehand or handle them gracefully using regex which is possible.

I am working on this one right now and came to the same conclusion. According to the answer in the unit test, it would seem that this particular output in incorrect. From reading the other outputs I inferred that the sorting should be by length and then lexicographically, this output (that user Arazai pointed out) seems to be incorrect based on that assumption.
Please consider making more precise instructions.

Had similar issue, to pass the kata it is enough to return empty string when there is no match. The description should be ammended to reflect those testcases.

When combinations fail, do more maths.

Combinatorics are usually VERY expensive, going up to n! in complexity; divide et impera: think how you would solve smaller problems, like finding if "abab" and "baab" are the same base string or not.

I got a brute force solution to work: getting all the permutations possible for the given input and then using a regex to test each and every single one of them. It is not very efficient and won't pass the test within the given time allowed by the test server.

Any suggestions on approaches that would be less expensive than brute force ?

You should change your approach as your algorithm will not pass the last test (actually it will break half-way). You won't be able to calculate factorial(1,000,000,000) in 12 seconds.

I was able to pass all the tests with a Python3 Solution, but still got an error message :

Traceback (most recent call last):
File "main.py", line 16, in
Test.assert_equals(FileNameExtractor.extract_file_name(s),ex,"It should work for random inputs too")
File "/home/codewarrior/solution.py", line 15, in extract_file_name
return query.group(2) + query.group(3)[:-1]
AttributeError: 'NoneType' object has no attribute 'group'

This would seem to indicate that the re expression is getting no matches, but yet it works find in my IDE.

I just did this kata and had a similar solution to those posted(though longer and uglier). It only works for 4 digit prices though. When I ran my solution I came across a bunch of prices with 5 or 3 digits, which messed up my whole algorithm . It was not clear to me that there would be prices of varying length (which make the re pattern more complex and this kata way harder)

I don't know about your code but here's some tips for Python or any other languages:
1.) look up LCM and GCD (math terms)
2.) in Python, be sure to use integer division when warranted, as opposed to float, I had some problems in python with that ...
3.)as a sidenote, there are some efficient algorithms apparently that compute GCD with heavy usage of bitwise operations, but traditinoal recursive GCD such as found in "Introduction to Algorithms" Cormen,Leiserson, Rivest seemed to work for me.

Based on your description i think i faced the same problem. In Python3 / (truediv()) returns float. Use // for integer division (floordiv()). You can also change the interpreter version above the editor area.