Efficiently find smallest unique substring
You can try suffix array approach which find all suffix of a given string of length n in O(n) time.
There are many algorithm to construct suffix array from a given input string.
Look at complete taxonomy here
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

For your problem you can use suffix array couple with some additional counter to find solution.