#JavaScript (ES7), 77 76 bytes
Takes input as a string.
f=(n,k)=>([...[k*k]+k**3].sort()+f).match([...n].sort().join`.*`)?k:f(n,-~k)
Arnauld
- 197.6k
- 20
- 179
- 650