128. Repeated DNA Sequences

Medium · String

You're given a DNA string containing only the characters A, C, G, and T. Your task is to find every distinct 10-letter substring that appears more than once in the string. Return all such substrings sorted in lexicographical (alphabetical) order.

Input: A single line containing a DNA string (characters A, C, G, T only).

Output: An array of strings, where each string is a 10-letter substring that occurs at least twice in the input, sorted lexicographically. If no substring repeats, return an empty array.

Examples

Example 1
Input: "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Explanation: Both substrings appear twice; return them sorted

Example 2
Input: "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
Explanation: Only one 10-letter substring repeats

Constraints

• Standard input/output constraints apply