Practice/Google/Leetcode 187. Repeated DNA Sequences

Leetcode 187. Repeated DNA Sequences

CodingOptional

Problem

You are analyzing a DNA sequence represented as a string containing only the characters 'A', 'C', 'G', and 'T'. Your task is to identify all 10-character-long subsequences that appear more than once in the given DNA string.

Return a list of all such duplicate sequences. The order of sequences in the output does not matter, but each duplicate sequence should appear only once in the result.

Requirements

1. Scan through the DNA string and identify all 10-character substrings
2. Track which sequences appear more than once
3. Return each duplicate sequence exactly once (no duplicates in the result)
4. Handle DNA strings of varying lengths efficiently

Constraints

• 1 ≤ s.length ≤ 100,000
• s consists only of 'A', 'C', 'G', and 'T'
• The returned list can be in any order
• Each distinct repeated sequence should appear exactly once in the output

Examples

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" Output: ["AAAAACCCCC", "CCCCCAAAAA"] Explanation: "AAAAACCCCC" appears at indices 0 and 10. "CCCCCAAAAA" appears at indices 5 and 15.

Example 2:

Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"] Explanation: The 10-character sequence "AAAAAAAAAA" appears 4 times starting at indices 0, 1, 2, and 3.

Example 3:

Input: s = "ACGTACGTAC" Output: [] Explanation: The string is only 10 characters long, so there is only one possible 10-character substring, which doesn't repeat.