ในปัญหานี้ เราได้รับอาร์เรย์ของตัวอักษรทั้งหมดเป็นตัวพิมพ์เล็ก งานของเราคือ การหาจำนวนการเกิดซ้ำสูงสุดของ Prefix ในอาร์เรย์
เราต้องนับจำนวนครั้งที่เกิดของ prefix ที่ไม่ว่างซึ่งมีจำนวนการเกิดมากที่สุด
ตัวอย่างเพื่อความเข้าใจ
Input : string = "xyyzkxyyzk" Output : 2
แนวทางแก้ปัญหา
ตรรกะคือการจินตนาการว่า prefix ของอาร์เรย์จะต้องประกอบด้วยตัวอักษรตัวแรกของสตริงเสมอ และการเกิดซ้ำของ prefix ก็จะมีตัวอักษรตัวแรกเช่นกัน ดังนั้น prefix ที่เกิดซ้ำมากที่สุดจะต้องเป็นตัวอักษรตัวแรกของสตริงโดยนิยามแล้ว งานจึงกลายเป็นการนับความถี่ของตัวอักษรตัวแรกในสตริง
อัลกอริทึม
- อ่านสตริงตัวพิมพ์เล็ก
- สร้างฟังก์ชันคืนค่าจำนวนของ prefix ที่ต้องการ
- กำหนด count = 0
- หาความถี่ของตัวอักษรตัวแรกของสตริง
- พิมพ์ความถี่ของตัวอักษรตัวแรก ซึ่งจะเป็นจำนวนการเกิดซ้ำสูงสุดของ prefix
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int findPrefixOccurence(string str) {
char chars = str[0];
int countOccrence = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == chars)
countOccrence++;
}
return countOccrence;
}
int main() {
string str = "xyyzxxyyzxyxx";
cout << "The maximum occurence of prefix in the array is " << findPrefixOccurence(str);
return 0;
}
ผลลัพธ์
The maximum occurence of prefix in the array is 6
