Nhờ cao nhân giúp đỡ về C++
Em có đề bài tìm Số ký tự tối thiểu để chèn bất cứ nơi nào trong chuỗi để tạo ra dãy a->z
Em đã code nhiều lần nhưng chạy không đúng và rất phức tạp
Mong các bác giúp đỡ, gợi ý giúp em với ạ
A string of lowercase letters is called alphabetical if deleting
zero or more of its letters can result in the alphabet string
“abcdefghijklmnopqrstuvwxyz”.
Given a string s, determine the minimum number of letters to
insert anywhere in the string to make it alphabetical.
Input
The input file contains several test cases, each of them consists of a single line containing a string s
(1 ≤ |s| ≤ 50).
It is guaranteed that s consists of lowercase ASCII letters ‘a’ to ‘z’ only.
Output
For each test case, print, on a single line, a single integer indicating the minimum number of letters
that must be inserted in order to make the string s alphabetical.
Sample Input
xyzabcdefghijklmnopqrstuvw
aiemckgobjfndlhp
Sample Output
3
20
Link: https://icpcarchive.ecs.baylor.edu/external/79/7953.pdf
Em cảm ơn các bác
Em up code của mình nên, mọi người cùng thảo luận nhé!
Mình cho bạn thuật toán này xem có khó code không nhé:
1. Trong dãy ban đầu, mỗi lần dãy không tăng (Input[i] ≤ Input[i-1]) thì ngắt ra thành dãy mới, thu được n dãy tăng.2. Trong n dãy tăng này, gọi x là số phần tử lớn nhất của một dãy tăng.3. return 26 - x;Nếu bạn không nghĩ được tại sao mình có thuật toán này thì có thể hỏi, mình hoặc người khác sẽ trả lời.
cái test case 2 làm sao nó ra 20 nhỉ, ai giải thích với ?
Bài này là tìm dãy tăng dài nhất rồi lấy 26 - chiều dài của dãy tăng đó :v OK thanks Trần Hoàn