Đếm substring không chứa đồng thời 'a', 'b', 'c' trong C++

Cho chuỗi str[] chỉ chứa 'a', 'b', 'c'. Đếm số substring không chứa cả ba ký tự cùng lúc. Substring hợp lệ: "a", "b", "c", "abb", "bba", "bc", "ca", "ccc" nhưng không phải "abc", "bcca", "cab".

Ví dụ

Đầu vào − str[] = "aabc"

Đầu ra − 8

Giải thích − "a", "a", "b", "c", "aa", "ab", "bc", "aab".

Đầu vào − str[] = "abcabc"

Đầu ra − 11

Giải thích − "a", "b", "c", "a", "b", "c", "ab", "bc", "ca", "ab", "bc".

Phương pháp giải

Tổng substring = n*(n+1)/2. Duyệt chuỗi, giữ vị trí cuối cùng của 'a', 'b', 'c' (a, b, c). Khi gặp 'a', cập nhật a = i+1, trừ min(b, c) khỏi count (loại bỏ các substring chứa cả ba). Tương tự cho 'b' và 'c'.

• Hàm sub_without_all(char str[], int size).
• count = size*(size+1)/2.
• a = b = c = 0.
• Duyệt i = 0..size-1:
  • Nếu str[i]=='a': a=i+1; count -= min(b,c);
  • Nếu str[i]=='b': b=i+1; count -= min(a,c);
  • Nếu str[i]=='c': c=i+1; count -= min(a,b);
• Trả về count.

Ví dụ code

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

int sub_without_all(char str[], int size) {
    int count = size * (size + 1) / 2;
    int a = 0, b = 0, 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;
}

Đầu ra

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