If you don't want the same element twice (OP's question), the best answer is zerozero nine's: shuffle the list first and that's done, no need to use random.choice. O(n) total.

If you want the same element twice, non need to use a set, just use random.choice on the string directly. O(1) for each choice.

If you really want to use random.choice on a set : random.choice(list(S)), but with complexity O(n) for each choice