นับ Substring ที่ตัวแรกและตัวสุดท้ายเหมือนกันใน C++

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

ตัวอย่าง

อินพุต: str = "abaefgf"

เอาต์พุต: 9

คำอธิบาย: "a", "b", "a", "e", "f", "g", "f", "aba", "fgf"

อินพุต: str = "abcdef"

เอาต์พุต: 6

คำอธิบาย: "a", "b", "c", "d", "e", "f" (แต่ละตัวนับเป็น substring ความยาว 1)

แนวทางการแก้ปัญหา

วิธีแบบง่าย (Naive O(n³))

สร้าง substring ทุกคู่ ตรวจสอบตัวแรกและตัวสุดท้าย

วิธีที่มีประสิทธิภาพ (O(n))

นับความถี่ของแต่ละตัวอักษร (freq[c]) สำหรับแต่ละตัวอักษรที่มีความถี่ f จำนวน substring ที่เริ่มและจบด้วยตัวอักษรนั้น = f × (f + 1) / 2 (เลือก 2 index จาก f index + substring ความยาว 1)

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

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

#define MAXIMUM 26

int check_Start_End(string str, int length) {
    int count = 0;
    int arr[MAXIMUM] = {0};
    
    // นับความถี่
    for (int i = 0; i < length; i++) {
        arr[str[i] - 'a']++;
    }
    
    // คำนวณจำนวน substring
    for (int i = 0; i < MAXIMUM; i++) {
        count += arr[i] * (arr[i] + 1) / 2;
    }
    return count;
}

int main() {
    string str = "bcbdedfef";
    int length = str.length();
    cout << "Count of substrings with same first and last characters are: " << check_Start_End(str, length);
    return 0;
}

เอาต์พุต

Count of substrings with same first and last characters are: 13