Earlier quoted context omitted.
That's what I suggested with >> Scan the entire internet for domains pointing to s3-website, and check AWS API to see if it's available? What I wonder is how do you scan all the DNS records with their subdomains? Unlike IPv4 address space, which is very decidedly finite and not-too-big, the space of all the subdomains is basically infinite. Other than using AXFR (zone-transfer DNS request) which is usually restricted…
There are size and character limits on DNS, so it's not infinite, although it may still be a pretty large space. Charts.(something well known) could have been a dictionary check though. AXFR makes it a lot easier though.
Still, we are looking at roughly 38*255 possible options (a-z, 0-9, a hyphen and dot to separate labels; "roughly" because each label between periods can be up to 64 characters, labels must be non-empty, and hyphens can't start a label).
As you said, it's pretty large: compared to 2*32 of IPv4 or even 2*128 of IPv6, this is more than (2*5)*255 = 2*1275 options.