if ($word =~ /[$random_string]$/i)

That only checks the last character from $word.

I don't think regexes are a good tool for the job. Instead keep a hash of how often each character may appear in the string. Iterate through all characters of the string, and for each character check if it's still allowed. If no, give out an error message. If yes, decrease the allowed count for that character.