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

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.

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 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.

Input is [[1, 1], [3, 1], [4, 1], [5, 1]]