ในปัญหานี้ เราได้รับอาร์เรย์ของอักขระทั้งหมดเป็นตัวพิมพ์เล็ก งานของเราคือ จำนวนคำนำหน้าในอาร์เรย์สูงสุด .
เราจำเป็นต้องนับการเกิดขึ้นของคำนำหน้าที่ไม่ว่างเปล่าซึ่งมีจำนวนการเกิดขึ้นสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : string = “xyyzkxyyzk” Output : 2
แนวทางการแก้ปัญหา
ตรรกะคือการนึกภาพว่าคำนำหน้าของอาร์เรย์ต้องมีอักขระตัวแรกของสตริงเสมอและแน่นอนว่าจะต้องเกิดขึ้นซ้ำ ๆ และอักขระตัวแรกของสตริงก็คือคำนำหน้าโดยมีจำนวนอักขระน้อยที่สุด ดังนั้นคำนำหน้าที่เกิดขึ้นสูงสุดจะเป็นอักขระตัวแรกของสตริงอย่างแน่นอน ตอนนี้งานลดลงเพื่อค้นหาการนับตัวอักษรตัวแรกในสตริง
อัลกอริทึม
-
อ่านสตริงของตัวอักษรพิมพ์เล็ก
-
สร้างฟังก์ชันเพื่อคืนค่าจำนวนคำนำหน้าที่ต้องการ
-
เริ่มนับ=0.
-
หาความถี่ของอักขระตัวแรกของสตริง
-
พิมพ์ความถี่ของอักขระตัวแรกของสตริงซึ่งในที่สุดจะเป็นการเกิดขึ้นสูงสุดของคำนำหน้าของสตริง
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
