[1291. Sequential Digits](https://leetcode.com/problems/sequential-digits/description/)

# 1. Tóm tắt đề bài

Cho hai biên $low$*(ie)* và $high$. Hãy tìm tất cả các số có tính chất đặc biệt được mô tả như dưới, mà thuộc khoảng giữa hai biên này?

- Với mỗi chữ số trong dãy, ngoại trừ chữ số đầu tiên, đều lớn hơn chữ số đằng trước 1 đơn vị.

Chẳng hạn: $789, 1234, 56$ đều là những số đặc biệt.

##### Giới hạn

$10 \le low \le high \le 10^9$.

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(1)$**

Nếu ta xét từng số một để xem nó có phải chữ số đặc biệt không => quá thời gian, do khoảng cách giữa $low$ và $high$ có thể lên quá $10^8$.

Vì vậy, ta cần thay đổi cách quan sát:

- Mỗi số đặc biệt có thể xác định bằng hai số: $(d, l)$, với $d$ ứng với giá trị chữ số đầu tiên, và $l$ là độ dài.
- Với $d$ chỉ trong khoảng $1$ đến $9$ (do số không thể bắt đầu bằng $0$), và $l$ trong khoảng $2$ đến $9$, ta có thể sinh ra mọi số đặc biệt trong bài.

# 3. Lời giải chi tiết

Mình sẽ tận dụng `string` và hàm `substr` ở bài toán này để code cho gọn, tập trung vào tính đúng đắn của thuật toán.

- Đầu tiên, mình khai báo `digits = "123456789"` rồi duyệt lấy tất cả `substr` có độ dài lớn hơn bằng $2$.
- Sau đó, với mỗi số, mình dùng hàm `stoi` của C++ để đổi sang dạng nguyên và so sánh với hai biên.
- Cuối cùng, tùy theo cách duyệt, mình sẽ phải sort lại mảng lưu kết quả. Tuy nhiên, nếu các bạn ưu tiên duyệt $l$ từ bé đến lớn trước, xong duyệt $d$ từ bé đến lớn sau, ta sẽ không phải `sort`, vì kết quả đã được đánh giá theo thứ tự tăng dần.

Code mẫu: https://leetcode.com/problems/sequential-digits/submissions/1163506761/

### Độ phức tạp thuật toán

Thời gian: $O(1)$

Bộ nhớ mở rộng: $O(1)$

**Lưu ý độ phức tạp**: Các bạn giải thích được tại sao, mặc dù dùng nhiều vòng lặp, ở bài toán này mình lại viết ĐPT là $O(1)$ không?

# 4. Kết luận & Gợi ý mở rộng

Đây là một bài toán đổi góc nhìn khá hay. Các bạn lưu ý cho mình phần đánh giá độ phức tạp nhé, bởi đây có thể là phần mà các bạn mắc bẫy trong các bài phỏng vấn chỉ vì chưa hiểu bản chất của việc tính toán ĐPT.

Một số bài tập mở rộng:

[2171. Removing Minimum Number of Magic Beans](https://leetcode.com/problems/removing-minimum-number-of-magic-beans/description/)
[2242. Maximum Score of a Node Sequence](https://leetcode.com/problems/maximum-score-of-a-node-sequence/description/)