Repeated DNA Sequences
NVIDIA● MediumFULLTIMEPHONE SCREENProblem statement
Given a DNA string s containing only A, C, G and T, return every distinct contiguous substring of exactly 10 characters that appears at least twice.
- Occurrences at different starting positions count separately, even when they overlap.
- Return each repeated substring exactly once, in ascending lexicographic order using
A < C < G < T. - Match the characters exactly. Reversed strings and reverse complements are not equivalent.
- If no substring repeats, including when
s.length < 10, return an empty array.
What the interview report shared
The live interview report names the standard repeated DNA sequence coding exercise and mentions follow-ups on corner cases, time complexity and space complexity. It does not enumerate the follow-up cases.
Explain the time and auxiliary space of your solution, including how many different windows it stores and any work used to order the result.
Function
findRepeatedDnaSequences(s: String) → String[]Examples
Example 1
s = "ACGTACGTACGTACGT"return = ["ACGTACGTAC","CGTACGTACG","GTACGTACGT"]The windows starting at 0, 1 and 2 reappear at 4, 5 and 6. The window at 3 appears once.
Example 2
s = "TTTTTTTTTTT"return = ["TTTTTTTTTT"]The two length-10 windows begin at 0 and 1. They overlap and have identical text, so the result contains that text once.
Example 3
s = "ACGT"return = []The string is shorter than 10, so it has no complete window.
Constraints
0 <= s.length <= 2000.- Every character of
sis one ofA,C,GorT.