It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least 2{n/2-2} states (the known upper bound is 2n), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least 2{sqrt{2n+30}-6} states. A similar state complexity function for scattered superstrings is determined to be exactly 2{n-2} + 1 for an alphabet of at least n-2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least 1/5 4sqrt{n/2}n-3/4.