Trying out all possible solutions from biggest to smallest would fit in the time limit.

To check if the solution is okay, you need to find out if it's valid and matches every character