สมมติว่าเรามีสตริงที่มีความยาว n ประกอบด้วยอักษรตัวพิมพ์ใหญ่เท่านั้น เราต้องหาจำนวนสตริงย่อยที่มีอักขระเรียงตามลำดับตัวอักษร ขนาดต่ำสุดของสตริงย่อยจะเป็น 2 ดังนั้นหากสตริงมีลักษณะดังนี้:“REFJHLMNBV” และจำนวนสตริงย่อยคือ 2 จะเป็น “EF” และ “MN”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตรวจสอบว่า str[i] + 1 เหมือนกับ str[i+1] หรือไม่ ถ้าใช่ ให้เพิ่มผลลัพธ์เป็น 1 และวนซ้ำสตริงจนถึงอักขระถัดไปซึ่งไม่เรียงตามลำดับตัวอักษร มิฉะนั้นให้ดำเนินการต่อ
ตัวอย่าง
#include<iostream>
using namespace std;
int countSubstr(string main_str) {
int res = 0;
int n = main_str.size();
for (int i = 0; i < n - 1; i++) {
if (main_str[i] + 1 == main_str[i + 1]) {
res++;
while (main_str[i] + 1 == main_str[i + 1]) {
i++;
}
}
}
return res;
}
int main() {
string str = "REFJHLMNBV";
cout << "Number of substrings: " << countSubstr(str);
} ผลลัพธ์
Number of substrings: 2
