Shortest, lexicographically smallest generating string
Ruby 1.9, 40 characters

gets;a=?a;a.next!until(a*~/$/)[$_];$&gt;&lt;&lt;a


Assumes the input is not terminated by a newline. Also it's probably ridiculously slow for larger results.

$ echo -n "bcabcabca" | ruby genlex.rb 
abc
$ echo -n "barfoobarfoobarfoo" | ruby1.9 genlex.rb 
arfoob