นับจำนวนสับสตริงที่มีตัวอักษรต่างกัน k ตัวด้วย C++

ได้รับสตริง str[] ที่มีตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น และค่าจำนวนเต็ม k เป้าหมายคือหาจำนวนสับสตริง (substring) ของ str ที่มีตัวอักษรต่างกัน (distinct characters) อยู่ที่ k ตัวพอดี

ตัวอย่าง

Input

str="pqr" k=2

Output

Count of number of substrings with exactly k distinct characters are: 2

Explanation

The substrings having exactly 2 distinct elements are: "pq", "qr".

Input

str="stristr" k=4

Output

Count of number of substrings with exactly k distinct characters are: 10

Explanation

The substrings having exactly 2 distinct elements are: "stri", "tris", "rist", "istr", "stris", "trist", "ristr", "strist", "tristr", "stristr".

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้อาร์เรย์ array[26] เก็บความถี่ของตัวอักษรภาษาอังกฤษภายในสตริง str วนลูป str ด้วยลูป for สองชั้น ถ้าสำหรับสับสตริง แต่ละตัวอักษรเกิดขึ้นครั้งเดียว ให้เพิ่มจำนวนนับตัวอักษรที่ไม่ซ้ำ เมื่อสิ้นสุดสับสตริงนั้น ถ้าจำนวนนับเท่ากับ k ให้เพิ่มจำนวนนับสับสตริงที่ตรงเงื่อนไข

• รับสตริง str เป็นอินพุต
• รับจำนวนเต็ม k ที่เป็นบวก
• ฟังก์ชัน substring_k(string str, int length, int k) คืนค่าจำนวนสับสตริงที่มีตัวอักษรต่างกัน k ตัว
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• สร้างอาร์เรย์ความถี่ array[26]
• วนลูป str ด้วยลูปสองชั้น i=0 ถึง length และ j=i ถึง length
• เก็บ temp เป็นจำนวนตัวอักษรที่ไม่ซ้ำในสับสตริง str[i ถึง j]
• ถ้า array[str[j] - 'a'] == 0 แสดงว่าตัวอักษรนี้เจอครั้งแรกในสับสตริงนี้ เพิ่ม temp
• เพิ่มความถี่ตัวอักษรปัจจุบัน array[str[j] - 'a']++
• ถ้า temp เท่ากับ k เพิ่ม count
• ถ้า temp มากกว่า k หยุดคำนวณต่อและ break ลูป
• เมื่อลูปจบ คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of number of substrings with exactly k distinct characters are: 3