there are other ways than permutation. I thought of that as well but the kata sensei provided a hint that says the number could be very large and by that permutation is impossible because of the time constraints.

This is a form of brute force solution. What you need is an efficient way to detect if there is a "next-smaller" -and- if so, how to transform the digits in the input in a single pass instead of searching the entire set of all permutations. It might help you to try doing smaller ones by hand to determine a pattern -- what's the next-smaller of 7012?