You could ask at kata solving chat for some advice, because posting here might be considered a spoiler.
To solve this kata, I was able to use an approach very similar to other, much simpler 2 kyu (terribly overranked tho) task. Many people went some (IMO) harder way.

Great Kata!
Took me 5 days to solve though.
I couldn't concentrate on other things as this kept bothering my brain.

These 3 seconds might be time needed for compilation and startup, but once it's done, efficient solution should not take too long to pass all test cases.
Unfortunately I have not solved it in C++ so I'd have to create solution from scratch to verify it, but as far as I see it was solved in C++ quite recently, so I would rather expect the problem to be in your solution.
You can print something to console on every invocation of your function (remember to flush), so you would know how far it gets before timing out.

My code passes 2 test cases and then times-out.
The example test takes ~3000ms, but it takes ~3000ms even if I reset everything to the initial state.

Is this time-out caused by the inefficiency of my code, or is it something else?
(I am using C++).