เราได้รับสตริง str เป้าหมายคือการนับจำนวนสตริงย่อยใน str ที่มีอักขระแต่ละตัวเกิดขึ้นสูงสุด k ครั้ง ตัวอย่างเช่น หากอินพุตคือ "abc" และ k=1 สตริงย่อยจะเป็น "a", "b", "c", "ab", "bc", "abc"
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − str=”abaefgf”
ผลผลิต − จำนวนสตริงย่อยที่มีอักขระตัวแรกและตัวสุดท้ายเหมือนกันคือ &mmius; 9
คำอธิบาย − สตริงย่อยจะเป็น
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
ป้อนข้อมูล − str=”abcdef”
ผลผลิต − จำนวนสตริงย่อยที่มีอักขระตัวแรกและตัวสุดท้ายเหมือนกันคือ:6
คำอธิบาย − สตริงย่อยจะเป็น -
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
อาจมีหลายวิธีในการแก้ปัญหาที่กำหนด เช่น แนวทางไร้เดียงสาและแนวทางที่มีประสิทธิภาพ มาดูแนวทางไร้เดียงสากันก่อน เราจะส่งต่อสตริงย่อยทุกความยาวไปยังฟังก์ชัน check() หากสตริงย่อยนั้นเริ่มต้นและลงท้ายด้วยอักขระเดียวกัน ให้เพิ่มจำนวนขึ้น
-
ใช้สตริง str. คำนวณความยาวเป็น str.size()
-
การตรวจสอบฟังก์ชัน (สตริง str) รับสตริงย่อย str และตรวจสอบว่าอักขระตัวแรกและตัวสุดท้ายเหมือนกันหรือไม่ ( str[0]==str[length-1] ) ถ้าเป็นจริง ให้คืนค่า 1.
-
ฟังก์ชัน check_Start_End(string str, int length) รับ str และความยาวเป็นอินพุต และคืนค่าจำนวนสตริงย่อยของ str ที่ขึ้นต้นและลงท้ายด้วยอักขระเดียวกัน
-
นับเริ่มต้นเป็น 0
-
Traverse str โดยใช้ two for loops จาก i=0 ถึง i
-
เราจะได้ substrings ทั้งหมดโดยใช้ substr(i,j) ทุกความยาว ส่งผ่านแต่ละสตริงย่อยเพื่อตรวจสอบ () หากคืนค่า 1 ให้นับเพิ่มขึ้น
-
เมื่อสิ้นสุดการนับลูปทั้งสองจะมีสตริงย่อยของ str จำนวนหนึ่งที่มีอักขระเริ่มต้นและสิ้นสุดเหมือนกัน
-
ผลตอบแทนนับเป็นผลลัพธ์ที่ต้องการ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
int count = 0;
int arr[26];
for (int i = 0; i < len; i++){
memset(arr, 0, sizeof(arr));
for (int j = i; j < len; j++){
arr[str[j] - 'a']++;
if (arr[str[j] - 'a'] <= k)
{ count++; }
else
{ break; }
}
}
return count;
}
int main(){
string str = "bbddehj";
int k = 1;
int length = str.length();
cout<<"Count of substrings with each character occurring at most k times are: "<<count_k(str,
length, k);
return 0;
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of substrings with each character occurring at most k times are: 14
