กำหนดสตริง str[] ที่มีตัวอักษรพิมพ์เล็กเท่านั้นและค่าจำนวนเต็ม k เป้าหมายคือการค้นหาจำนวนสตริงย่อยที่เป็นไปได้ของ str ที่มีองค์ประกอบที่แตกต่างกัน k ตัว
ตัวอย่าง
อินพุต
str= ”pqr” k=2
ผลลัพธ์
Count of number of substrings with exactly k distinct characters are: 2
คำอธิบาย
The substrings having exactly 2 distinct elements are: “pq”, “qr”.
อินพุต
str= ”stristr” k=4
ผลลัพธ์
Count of number of substrings with exactly k distinct characters are: 10
คำอธิบาย
The substrings having exactly 2 distinct elements are: “stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะใช้อาร์เรย์อาร์เรย์[26] เพื่อเก็บความถี่ของตัวอักษรภาษาอังกฤษไว้ในสตริง str ตอนนี้ข้าม str โดยใช้สองลูป ถ้าสำหรับสตริงย่อย อักขระแต่ละตัวจะเกิดขึ้นครั้งเดียว จากนั้นเพิ่มจำนวนอักขระที่ไม่ซ้ำ ที่ส่วนท้ายของสตริงย่อยนั้นหากการนับนั้นเท่ากับ k ให้นับสตริงย่อยเพิ่มขึ้นตามเงื่อนไขที่กำหนด
-
รับสตริงสตริงเป็นอินพุต
-
หาจำนวนเต็ม k ด้วยค่าบวก
-
ฟังก์ชัน substring_k(string str, int length, int k) รับ str และ k และคืนค่าจำนวนสตริงย่อยที่มีอักขระต่างกัน k ตัว
-
นับเริ่มต้นเป็น 0
-
ใช้อาร์เรย์อาร์เรย์ความถี่[26].
-
ข้าม str โดยใช้สองลูปจาก i=0 ถึง i
-
ใช้ temp เป็นจำนวนองค์ประกอบที่ไม่ซ้ำในสตริงย่อย str[i ถึง j]
-
หาก array[str[j] − 'a']==0 แสดงว่าอักขระนี้ str[j] เกิดขึ้นครั้งแรกในสตริงย่อยนี้ อุณหภูมิที่เพิ่มขึ้นดังนั้น
-
ตอนนี้เพิ่มจำนวนอักขระปัจจุบันโดยใช้ array[str[j] - 'a']++
-
หากอุณหภูมิเท่ากับ k ให้นับการเพิ่ม
-
หากอุณหภูมิมากกว่า k ให้หยุดการเดินทางต่อไปและทำลายวงจร
-
ที่ส่วนท้ายของการวนซ้ำทั้งหมดจะนับเป็นผลลัพธ์
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int substring_k(string str, int length, int k){
int count = 0;
int array[26];
for (int i = 0; i < length; i++){
int temp = 0;
memset(array, 0, sizeof(array));
for (int j = i; j < length; j++){
if(array[str[j] − 'a'] == 0){
temp++;
}
array[str[j] − 'a']++;
if (temp == k){
count++;
}
if(temp > k){
break;
}
}
}
return count;
}
int main(){
string str = "abc";
int length = str.length();
int k = 1;
cout<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of number of substrings with exactly k distinct characters are: 3
