Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

DNA Pattern Recognition solution and explanation

MediumDatabase6 min read85.5% acceptanceUpdated 16 Oct 2026
Practise DNA Pattern Recognition
6:21
Leetcode MEDIUM 3475 - Using REGEX in SQL - DNA Pattern Recognition | Everyday Data ScienceEveryday Data Science · 6:21 · 918 viewsWatch on YouTube
3 more videos on this problem
  1. Leetcode MEDIUM 3475 - Using REGEX in SQL - DNA Pattern Recognition | Everyday Data ScienceEveryday Data Science · 6:21 · 918 views
  2. Leetcode 3475. DNA Pattern RecognitionInsightVanta · 9:53 · 109 views
  3. LeetCode 3475 – DNA Pattern Recognition | Pandas | Leetcode Interview QuestionThe Knowledge Academy · 2:14 · 25 views
  4. Leetcode 3475 | Solving DNA Motif Problems: SQL CASE WHEN vs. Pandas .str.contains + regexDataHead Girl · 5:24 · 11 views

The problem

Table: Samples

+----------------+---------+
| Column Name    | Type    | 
+----------------+---------+
| sample_id      | int     |
| dna_sequence   | varchar |
| species        | varchar |
+----------------+---------+
sample_id is the unique key for this table.
Each row contains a DNA sequence represented as a string of characters (A, T, G, C) and the species it was collected from.

Biologists are studying basic patterns in DNA sequences. Write a solution to identify sample_id with the following patterns:

  • Sequences that start with ATG (a common start codon)
  • Sequences that end with either TAA, TAG, or TGA (stop codons)
  • Sequences containing the motif ATAT (a simple repeated pattern)
  • Sequences that have at least 3 consecutive G (like GGG or GGGG)

Return the result table ordered by sample_id in ascending order.

The result format is in the following example.

Example:

Input:

Samples table:

+-----------+------------------+-----------+
| sample_id | dna_sequence     | species   |
+-----------+------------------+-----------+
| 1         | ATGCTAGCTAGCTAA  | Human     |
| 2         | GGGTCAATCATC     | Human     |
| 3         | ATATATCGTAGCTA   | Human     |
| 4         | ATGGGGTCATCATAA  | Mouse     |
| 5         | TCAGTCAGTCAG     | Mouse     |
| 6         | ATATCGCGCTAG     | Zebrafish |
| 7         | CGTATGCGTCGTA    | Zebrafish |
+-----------+------------------+-----------+

Output:

+-----------+------------------+-------------+-------------+------------+------------+------------+
| sample_id | dna_sequence     | species     | has_start   | has_stop   | has_atat   | has_ggg    |
+-----------+------------------+-------------+-------------+------------+------------+------------+
| 1         | ATGCTAGCTAGCTAA  | Human       | 1           | 1          | 0          | 0          |
| 2         | GGGTCAATCATC     | Human       | 0           | 0          | 0          | 1          |
| 3         | ATATATCGTAGCTA   | Human       | 0           | 0          | 1          | 0          |
| 4         | ATGGGGTCATCATAA  | Mouse       | 1           | 1          | 0          | 1          |
| 5         | TCAGTCAGTCAG     | Mouse       | 0           | 0          | 0          | 0          |
| 6         | ATATCGCGCTAG     | Zebrafish   | 0           | 1          | 1          | 0          |
| 7         | CGTATGCGTCGTA    | Zebrafish   | 0           | 0          | 0          | 0          |
+-----------+------------------+-------------+-------------+------------+------------+------------+

Explanation:

  • Sample 1 (ATGCTAGCTAGCTAA):
    • Starts with ATG (has_start = 1)
    • Ends with TAA (has_stop = 1)
    • Does not contain ATAT (has_atat = 0)
    • Does not contain at least 3 consecutive 'G's (has_ggg = 0)
  • Sample 2 (GGGTCAATCATC):
    • Does not start with ATG (has_start = 0)
    • Does not end with TAA, TAG, or TGA (has_stop = 0)
    • Does not contain ATAT (has_atat = 0)
    • Contains GGG (has_ggg = 1)
  • Sample 3 (ATATATCGTAGCTA):
    • Does not start with ATG (has_start = 0)
    • Does not end with TAA, TAG, or TGA (has_stop = 0)
    • Contains ATAT (has_atat = 1)
    • Does not contain at least 3 consecutive 'G's (has_ggg = 0)
  • Sample 4 (ATGGGGTCATCATAA):
    • Starts with ATG (has_start = 1)
    • Ends with TAA (has_stop = 1)
    • Does not contain ATAT (has_atat = 0)
    • Contains GGGG (has_ggg = 1)
  • Sample 5 (TCAGTCAGTCAG):
    • Does not match any patterns (all fields = 0)
  • Sample 6 (ATATCGCGCTAG):
    • Does not start with ATG (has_start = 0)
    • Ends with TAG (has_stop = 1)
    • Starts with ATAT (has_atat = 1)
    • Does not contain at least 3 consecutive 'G's (has_ggg = 0)
  • Sample 7 (CGTATGCGTCGTA):
    • Does not start with ATG (has_start = 0)
    • Does not end with TAA, "TAG", or "TGA" (has_stop = 0)
    • Does not contain ATAT (has_atat = 0)
    • Does not contain at least 3 consecutive 'G's (has_ggg = 0)

Note:

  • The result is ordered by sample_id in ascending order
  • For each pattern, 1 indicates the pattern is present and 0 indicates it is not present

Approach overview

Problem Overview: You get a table of DNA sequences, and you need to return the rows whose sequence matches a set of required patterns. The patterns involve fixed prefixes, suffixes, and internal substrings. The job is to express those rules as a filter and let the database evaluate them per row.

Approach 1: Chained LIKE Conditions (O(n * L) time, O(1) extra space)

Write one LIKE clause for each rule, such as dna_sequence LIKE 'ATG%' for a prefix and LIKE '%TAA' for a suffix, then combine them with AND and OR. Each LIKE scans the string once, so the cost per row is proportional to the sequence length L. This is the easiest approach to read and debug. Use it when the rules are simple prefixes and suffixes and you want portable SQL. It breaks down once the rules include alternation or character classes, because LIKE cannot express them.

Approach 2: Regular Expressions in a Single Pattern (O(n * L) time, O(1) extra space)

Compile the whole rule set into one regex and apply it with REGEXP in MySQL or str.contains(pattern, regex=True) in Pandas. Anchor the pattern with ^ and $ for prefix and suffix checks, and use alternation like (TAA|TAG|TGA)$ for multiple stop codons. The engine handles the scan in one pass. This is the approach our platform recommends for this problem because it keeps the whole condition in one place and matches the way the rules are stated. Watch for case sensitivity and for patterns that overlap, since regex engines differ on how they handle them.

Approach 3: Fuzzy Matching for Near Misses (O(n * L * k) time, O(k) space)

If the requirement allows a small number of mismatches, use fuzzy matching. Compute an edit distance of at most k between the sequence and each target pattern, or use a sliding window that counts mismatched characters. This is heavier than the exact approaches and only makes sense when the problem explicitly asks for approximate matches. For exact-pattern problems, it adds cost without adding correctness.

Recommended for interviews: Start with the chained LIKE version to show you understand the filter logic. Then move to a single regex to show you can express the full rule set cleanly. The brute force shows you understand the requirements. The regex version shows you can write production-quality SQL. Mention the O(L) cost per row so the interviewer sees you know the scan is linear in sequence length.

Related topics: database, string, regular expression

Solution

Thinking

Four flags detect a start codon, a stop codon, ATAT, and at least three Gs in a row. String methods are shorter and safer than a manual scan.

startswith/endswith cover the ends; containment and GGG+ cover the interior patterns.

The four columns are 0/1, then the frame is sorted by sample_id, matching a SQL LIKE/REGEXP solution.

We can use LIKE and REGEXP for pattern matching, where:

  • LIKE 'ATG%' checks if it starts with ATG
  • REGEXP 'TAA<code>|TAG</code>|TGA<code>' checks if it ends with TAA, TAG, or TGA ( indicates the end of the string)
  • LIKE '%ATAT%' checks if it contains ATAT
  • REGEXP 'GGG+' checks if it contains at least 3 consecutive Gs
# Write your MySQL query statement below
SELECT
    sample_id,
    dna_sequence,
    species,
    dna_sequence LIKE 'ATG%' AS has_start,
    dna_sequence REGEXP 'TAA$|TAG$|TGA$' AS has_stop,
    dna_sequence LIKE '%ATAT%' AS has_atat,
    dna_sequence REGEXP 'GGG+' AS has_ggg
FROM Samples
ORDER BY 1;
import pandas as pd


def analyze_dna_patterns(samples: pd.DataFrame) -> pd.DataFrame:
    samples["has_start"] = samples["dna_sequence"].str.startswith("ATG").astype(int)
    samples["has_stop"] = (
        samples["dna_sequence"].str.endswith(("TAA", "TAG", "TGA")).astype(int)
    )
    samples["has_atat"] = samples["dna_sequence"].str.contains("ATAT").astype(int)
    samples["has_ggg"] = samples["dna_sequence"].str.contains("GGG+").astype(int)
    return samples.sort_values(by="sample_id").reset_index(drop=True)
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Chained LIKE ConditionsO(n * L)O(1)Simple prefix and suffix rules, portable SQL
Single Regex PatternO(n * L)O(1)Multiple alternatives, anchors, cleanest rule set
Fuzzy Matching (edit distance)O(n * L * k)O(k)Only when approximate matches with up to k errors are allowed

Frequently asked questions

DNA Pattern Recognition Python solution?

In Python with Pandas, load the table into a DataFrame, then filter with df[df['dna_sequence'].str.contains(pattern, regex=True)] using a compiled regex such as '^ATG.*(TAA|TAG|TGA)$'. This runs in O(n * L) time. Use the regex flag to match exact sequence rules.

Is DNA Pattern Recognition easy or hard?

It is rated medium on FleetCode with an acceptance rate of about 85.5 percent. The logic is straightforward once you translate the rules into a regex. The difficulty comes from getting the anchors, alternation, and case sensitivity right, not from algorithmic complexity.

How to solve DNA Pattern Recognition in O(n)?

Treat each sequence as a fixed-length scan and apply one combined regex with anchors for prefix and suffix checks. The cost per row is linear in the sequence length, so the total cost across the table is linear in the total number of characters. Use a single WHERE clause with REGEXP so the database filters rows in one pass.

What is the best approach for DNA Pattern Recognition?

The best approach is a single regular expression applied with REGEXP in MySQL or str.contains in Pandas. It evaluates all pattern rules in one scan per sequence. Chained LIKE conditions give the same result for simple prefix and suffix rules but become hard to maintain as the rules grow.

What data structure is used in DNA Pattern Recognition?

The input is a relational table, and the core structure is the sequence string in each row. The pattern rules are expressed as a regular expression, which is compiled into a finite automaton by the database engine. No custom data structure is needed beyond the table itself.

What is the time complexity of DNA Pattern Recognition?

The time complexity is O(n * L), where n is the number of rows and L is the average length of a DNA sequence. Each row is scanned once by the pattern engine. The extra space is O(1) beyond the output.

Is DNA Pattern Recognition asked at Google, Amazon, or Meta?

This problem is tagged Database on FleetCode and is a SQL-style pattern matching exercise. Company-specific interview data for this problem is not published, so check recent reports on company interview sites before assuming frequency. Practicing string filtering in SQL is useful for any role that involves querying text data.

Comments

Now write it yourselfClose this page and solve DNA Pattern Recognition in the editor, without looking.
Practise DNA Pattern Recognition