Elearning CodePath – CTP Online Judge

Khoảng cách "to" nhất

KCTN

🟢 Easy #General #String #Simulation #Brute Force #Sliding Window #Array #Optimization

### Thông tin chung

| Mục | Nội dung |
| --- | --- |
| **Tên Bài Toán** | **Khoảng cách "to" nhất** |
| **Input** | xâu s, số nguyên dương q, q số nguyên dương l và r |
| **Output** | q số nguyên dương là khoảng cách lớn nhất của xâu con liên tiếp từ $s_l$......$s_r$ |
| **File Input** | `KCTN.INP` |
| **File Ouput** | `KCTN.OUT` |

Năm nay Châu Khang Dương bước vào lớp $1$. Cậu rất thích thú khi được đi học, và đặc biệt thích học bảng chữ cái Tiếng Anh. Nhưng vì cậu học rất nhanh, nên khi thầy cô trên bảng giảng xong về chữ $b$, cậu đã thuộc lòng từ $a$ đến $z$. Quá chán vì thầy cô giảng chậm, cậu quyết định nghịch một chút với bảng chữ cái mới học này.

Cậu vẽ từng chữ cái một từ a đến z trên một vòng tròn. Đầu tiên viết chữ a, sau đó chữ b,.....Cuối cùng chữ z nằm bên trái chữ a.

Cậu quy ước rằng khoảng cách giữa hai chữ cái bất kì là khoảng cách ngắn nhất từ điểm của chữ cái này đến điểm của chữ cái kia trong vòng tròn vừa tạo. Ví dụ 'a' với 'd' có khoảng cách là $3$;  'a' với 'z' có khoảng cách là $1$.
		Sau đó cậu nhờ người ngồi cạnh mình, Giang Lăng Vũ, viết cho một xâu chỉ gồm các kí tự trong bảng chữ cái tiếng anh in thường.

Bỗng thầy giáo gọi cậu lên bảng và hỏi cậu đang làm gì. Cậu phổ biến cho mọi người về bảng chữ cái và xâu, sau đó cậu đề xuất một trò chơi thú vị hơn nhiều so với học chữ: Cho q truy vấn xác định bởi hai số l và r, hãy tìm khoảng cách lớn nhất của hai kí tự bất kì trong xâu con liên tiếp từ $s_l$...$s_r$.

Kevin, một cậu bạn học dốt nhất lớp, do vừa mới học xong chữ b, không biết phải làm thế nào, nên nhờ bạn chơi hộ trò chơi này.

### Định dạng đầu vào

- Dòng đầu là xâu s gồm toàn các chữ cái Tiếng Anh in thường
 
 - 1 <= $|S|$ <= $10^5$
- Dòng tiếp theo là số nguyên dương $q$
 
 - 1 <= $q$ <= $10^5$
- Tiêp theo là q dòng, mỗi dòng chứa hai số nguyên $l$,$r$ ($1$ <= $l$ <= $r$ <= $|S|$)

### Định dạng đầu ra

- In ra trên $q$ dòng. Dòng thứ $i$ là khoảng cách lớn nhất giữa hai kí tự bất kì của xâu con liên tiếp xét tại truy vấn thứ $i$.

### Ví dụ (Sample Test)

| Input (`KCTN.INP`) | Output (`KCTN.OUT`) |
| --- | --- |
| `abcyzz`  `3`  `1 3`  `2 5`  `5 6` | `2`  `4`   `0`  |

### Subtask:

- Có 50% số test $|S|$ <= $10^3$
 
- 50% số test còn lại không có ràng buộc gì thêm.

✅ Đã AC: 1 / 1 submissions