Xin ý tưởng thuật toán
Các nhà sinh học vừa phát hiện ra một loại cấu trúc DNA alpha đặc biệt được cấu trúc bởi chỉ các Nucleotit A và B. Đặc biệt hơn, họ còn phát hiện ra một loại gen omega chỉ gồm nucleotit A nhưng vô cùng hiếm, để nghiên cứu sâu hơn về omega họ quyết định tổng hợp omega từ alpha bằng các phương pháp đột biến nhân tạo. May mắn thay họ tìm ra hai phương pháp đột biến có thể gây ảnh hưởng đến alpha: họ có thể làm thay đổi 1 nuleotit ở một vị trí bất kỳ trên đoạn gen alpha (A thành B hoặc B thành A), phương pháp thứ hai là thay đổi cả đoàn đầu của gen (những nuc A chuyển thành B và ngược lại). Để tiết kiệm chi phí họ quyết định tìm ra số lần gây đột biến ít nhất có thể để biến alpha thành omega.
Hãy giúp họ.
Input
Dòng đầu tiên chứa số tự nhiên n là số nucleotit của gen alpha (1 <= n <= 1000000)
Dòng thứ hai là biểu diễn của gen alpha.
Output
Kết quả bài toán.
Example
Input:
12
AAABBBAAABBB
Output:
4
Plzzz. Mình hơi khó hiểu :v
Keyword của thuật toán này là Minimum Edit Distance.
<3 Cảm ơn đồng chí :v