Chuỗi Gen

Xem PDF

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 128M Input: bàn phím Output: màn hình

Hôm nay trong bài thơ khoa học của Vương quốc Kremland, đã có một bài học sinh học. Chủ đề của bài học là bộ gen. Hãy gọi bộ gen là chuỗi "ACTG".

Sắn rất nhàm chán khi ngồi trong lớp, vì vậy giáo viên đã đưa ra một nhiệm vụ cho anh ta: trên một chuỗi \(S\) bao gồm chữ in hoa và độ dài ít nhất 4, bạn cần tìm số lượng hoạt động tối thiểu mà bạn cần áp dụng, để bộ gen xuất hiện trong chuổi này dưới dạng một chuỗi con.

Đối với một thao tác, bạn có thể thay thế bất kỳ chữ cái nào trong chuỗi S với kí tự tiếp theo hoặc trước đó trong bảng chữ cái. Ví dụ: đối với chữ "D" thì chữ trước sẽ là "C" và chữ tiếp theo - "E". Trong vấn đề này, chúng tôi giả sử rằng đối với chữ "A", chữ cái trước sẽ là chữ "Z" và chữ tiếp theo sẽ là "B" và đối với chữ "Z", chữ trước là chữ "Y", và cái tiếp theo là chữ "A".

Giúp Sắn giải quyết vấn đề mà giáo viên đưa ra. Một chuỗi a là một chuỗi con của một chuỗi b nếu như a là một đoạn kí tự liên tiếp trong b.

Input

  • Dòng đầu tiên chứa một số nguyên \(n (4 \le n \le 5000)\) - độ dài của chuỗi \(S\).

  • Dòng thứ hai chứa chuỗi \(S\), bao gồm chính xác n chữ in hoa của bảng chữ cái Latin.

Output

  • Xuất số lượng hoạt động tối thiểu cần được áp dụng cho chuỗi S để bộ gen xuất hiện dưới dạng một chuỗi con trong đó.

Example

Test 1

Input
4
ZCTH
Output
2

Test 2

Input
5
ZDATG
Output
5

Test 3

Input
6
AFBAKC
Output
16

Bình luận

Không có bình luận nào.