If there were more distinct $k$-size substrings than possible $k$-size substrings, then at least one of these strings is impossible.
YES! You can assume that!
I'm assuming by "different" you mean "distinct", so for example if S = AABAB, we have two strings S[2,3] and S[4,5] which are "different substrings" but not "distinct" since both are AB.
I think you'll be stuck with that as a rather coarse upper bound, because how strings might be duplicated (via letter repetition) is going to get very computationally difficult as the size of your alphabet goes up.