นับ Substring ที่เริ่มต้นด้วย X และลงท้ายด้วย Y ใน C++

เราได้รับสตริง str และตัวอักษร X, Y เป้าหมายคือนับ substring ที่ขึ้นต้นด้วย X และลงท้ายด้วย Y

ตัวอย่าง

อินพุต: str = "abcccdef", X = 'a', Y = 'c'

เอาต์พุต: 3

คำอธิบาย: "abc", "abcc", "abccc"

อินพุต: str = "tempest", X = 't', Y = 't'

เอาต์พุต: 3

คำอธิบาย: "t", "tempest", "t" (นับทุกคู่ index ที่เป็น t)

แนวทางการแก้ปัญหา (O(n))

วนลูปสตริง นับจำนวน X ที่เจอมา (x_total) เมื่อเจอ Y ให้บวก x_total เข้าไปในคำตอบ (เพราะ X ทุกตัวที่เจอมาแล้ว สามารถจับคู่กับ Y ตัวนี้ได้)

การนำไปใช้ (Implementation)

#include <bits/stdc++.h>
using namespace std;

int X_Y(string str, int length, char X, char Y) {
    int count = 0;
    int x_total = 0;
    for (int i = 0; i < length; i++) {
        if (str[i] == X) x_total++;
        if (str[i] == Y) count += x_total;
    }
    return count;
}

int main() {
    string str = "defaabbcchhkl";
    int length = str.size();
    char X = 'd';
    char Y = 'a';
    cout << "Count of substrings that starts with character X and ends with character Y are: " << X_Y(str, length, X, Y);
    return 0;
}

เอาต์พุต

Count of substrings that starts with character X and ends with character Y are: 2