นับซับสตริงที่ไม่มีตัวอักษร a, b, c ครบทั้งสามพร้อมกันใน C++

เราได้รับสตริง str[] ที่มีแค่ 'a', 'b' และ 'c' เป้าหมายคือหาซับสตริงของ str[] ที่ตัวอักษรทั้งสามไม่ได้เป็นส่วนหนึ่งของซับสตริงนั้น สำหรับสตริงใดๆ ซับสตริงอาจเป็น "a", "b", "c", "abb", "bba", "bc", "ca", "ccc" แต่ไม่ใช่ "abc", "bcca", "cab" เพราะมี 'a', 'b', 'c' ครบทั้งสาม

มาดูตัวอย่าง

อินพุต − str[] = "aabc"

เอาต์พุต − จำนวนซับสตริงที่ไม่มีตัวอักษรจากเซต {a, b, c} ครบทั้งสามพร้อมกัน คือ 8

คำอธิบาย − ซับสตริงจะเป็น: "a", "a", "b", "c", "aa", "ab", "bc", "aab"

อินพุต − str[] = "abcabc"

เอาต์พุต − จำนวนซับสตริงที่ไม่มีตัวอักษรจากเซต {a, b, c} ครบทั้งสามพร้อมกัน คือ 11

คำอธิบาย − ซับสตริงจะเป็น: "a", "b", "c", "a", "b", "c", "ab", "bc", "ca", "ab", "bc"

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

ในแนวทางนี้เรารู้ว่าจำนวนซับสตริงทั้งหมดของสตริง n ตัวอักษรคือ n*(n+1)/2

เราจะเดินทางผ่านสตริงและสำหรับแต่ละประเภทตัวอักษร 'a', 'b' หรือ 'c' เราจะตรวจสอบดัชนีก่อนหน้าของอีกสองตัวอักษร ('b','c'), ('c','a') และ ('a','b') เพียงแค่ลบดัชนีต่ำสุดของอีกสองตัวออกจาก count เพราะเรารู้ว่าเรากำลังลบตัวอักษรนั้นเพื่อรวมตัวอักษรปัจจุบันในซับสตริงให้ไม่มีทั้งสามตัว

• รับสตริง str เป็นอาเรย์ตัวอักษร
• ฟังก์ชัน sub_without_all(char str[], int size) รับสตริง ความยาว คืนจำนวนซับสตริงที่ไม่มี 'a', 'b', 'c' พร้อมกัน
• กำหนด count เริ่มต้น size*(size+1)/2 สำหรับซับสตริงทั้งหมดที่เป็นไปได้
• ตัวแปร a,b,c เก็บดัชนีล่าสุดของ 'a', 'b', 'c' เริ่มต้นทั้งหมดเป็น 0
• ลูป FOR จาก i=0 ถึง i<size
• ถ้า str[i]=='a' อัปเดตดัชนี 'a' เป็น a=i+1 ลบค่าต่ำสุดของดัชนี 'b' หรือ 'c' ออกจาก count เพื่อรวม 'a' ในซับสตริง ลบ b,c ใดก็ตามที่น้อยกว่า
• ทำเหมือนขั้นตอนก่อนสำหรับ str[i]=='b' หรือ str[i]=='c'
• ท้ายสุด count คือซับสตริงของ str[] ที่ไม่มีทั้งสามตัวอักษรพร้อมกัน
• คืน count

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

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

int sub_without_all(char str[], int size){
    int update_size = size * (size + 1);
    int count = update_size / 2;
    int a, b, c;
    a = b = c = 0;
    for (int i = 0; i < size; i++){
        if (str[i] == 'a'){
            a = i + 1;
            count -= min(b, c);
        } else if (str[i] == 'b'){
            b = i + 1;
            count -= min(a, c);
        } else {
            c = i + 1;
            count -= min(a, b);
        }
    }
    return count;
}

int main(){
    char str[] = "abcabbc";
    int size = strlen(str);
    cout<<"Count of sub-strings that do not contain all the characters from the set {a, b, c} at the same time are: "<<sub_without_all(str, size);
    return 0;
}

เอาต์พุต

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

Count of sub-strings that do not contain all the characters from the set {a, b, c} at the same time are: 15