Problem

Description

Table: Products

+————-+———+ | Column Name | Type | +————-+———+ | product_id | int | | name | varchar | +————-+———+ product_id is the unique key for this table. Each row of this table contains the ID and name of a product.

Write a solution to find all products whose names contain a sequence of exactly three digits in a row.

Return the result table ordered by product_id in ascending order.

The result format is in the following example.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

**Input:**
products table:
+-------------+--------------------+
| product_id  | name               |
+-------------+--------------------+
| 1           | ABC123XYZ          |
| 2           | A12B34C            |
| 3           | Product56789       |
| 4           | NoDigitsHere       |
| 5           | 789Product         |
| 6           | Item003Description |
| 7           | Product12X34       |
+-------------+--------------------+
**Output:**
+-------------+--------------------+
| product_id  | name               |
+-------------+--------------------+
| 1           | ABC123XYZ          |
| 5           | 789Product         |
| 6           | Item003Description |
+-------------+--------------------+
**Explanation:**
- Product 1: ABC123XYZ contains the digits 123.
- Product 5: 789Product contains the digits 789.
- Product 6: Item003Description contains 003, which is exactly three digits.
**Note:**
- Results are ordered by `product_id` in ascending order.
- Only products with exactly three consecutive digits in their names are included in the result.

Example 2:

Solution

Method 1 – Regex Pattern Matching

Intuition

We need to find product names that contain a sequence of exactly three digits in a row. This can be efficiently done using a regular expression that matches three consecutive digits not part of a longer digit sequence.

Approach

  1. Use a regular expression to match names containing exactly three consecutive digits (not part of a longer digit sequence).
  2. In SQL, use REGEXP (MySQL) or ~ (PostgreSQL) to filter such names.
  3. Return the result ordered by product_id ascending.

Code

1
2
3
4

SELECT product_id, name
FROM Products
WHERE name REGEXP '[^0-9][0-9]{3}[^0-9]' OR name REGEXP '^[0-9]{3}[^0-9]' OR name REGEXP '[^0-9][0-9]{3}$' OR name REGEXP '^[0-9]{3}$'
ORDER BY product_id;
1
2
3
4

SELECT product_id, name
FROM Products
WHERE name ~ '(^|[^0-9])[0-9]{3}([^0-9]|$)'
ORDER BY product_id;
1
2
3
4
5
6
7

class Solution:
    def find_products_with_three_consecutive_digits(self, df):
        # df has columns: product_id, name
        import pandas as pd
        pat = r'(^|[^0-9])[0-9]{3}([^0-9]|$)'
        result = df[df['name'].str.contains(pat, regex=True)].copy()
        return result.sort_values('product_id')[['product_id', 'name']]

Complexity

  • ⏰ Time complexity: O(n), where n is the number of products, since each name is checked once.
  • 🧺 Space complexity: O(k), where k is the number of matching products in the result.