Find second-minimal word segmentation count

Given a string s and a dictionary D of non-empty words, define a 'segmentation' as splitting s into a sequence of words from D whose concatenation equals s. Let the cost of a segmentation be the number of words used. Return the second-smallest possible cost among all valid segmentations, or -1 if fewer than two valid segmentations exist. Only return the cost; do not enumerate segmentations. Describe your algorithm, justify its time and space complexity, and explain how you would handle large inputs.