Hi Brandon,
I would suggest using a completely different domain than the one that is actually also your main domain for your website.
Something like seamlesshostingpreview.co or whatever so you're not inviting funny shenanigans by letting people set sub domains up on your main domain.
Using a different one means you could use simply seamlesshostingpreview.co and then a customer can put whatever they want before it.
they could then enter staging.clientsname and it would be staging.clientsname.seamlesshostingpreview.co
Or essentially whatevertheyputinthefirstbox.seamlesshostingpreview.co