Chúng ta được cung cấp một chuỗi str [] chỉ chứa ‘a’, ‘b’ và ‘c’. Mục đích là tìm các chuỗi con của str [] sao cho cả ba ký tự không phải là một phần của chuỗi con đó. Đối với bất kỳ chuỗi str nào, các chuỗi con có thể là “a”, “b”, “c”, “abb”, “bba”, “bc”, “ca”, “ccc” nhưng không phải là “abc”, “bcca”, “ taxi ”vì chúng có 'a', 'b' và 'c', cả ba.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - str [] =“aabc”
Đầu ra - Số chuỗi con không chứa tất cả các ký tự từ tập hợp {‘a’, ‘b’, ‘c’} cùng một lúc là - 8
Giải thích - Các chuỗi con sẽ là:“a”, “a”, “b”, “c”, “aa”, “ab”, “bc”, “aab”
Đầu vào - str [] =“abcabc”
Đầu ra - Số lượng chuỗi con không chứa tất cả các ký tự từ tập hợp {‘a’, ‘b’, ‘c’} tại cùng một thời điểm là - 11
Giải thích - Các chuỗi con sẽ là:“a”, “b”, “c”, “a”, “b”, “c”, “ab”, “bc”, “ca”, “ab”, “bc”
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Theo cách tiếp cận này, chúng ta biết rằng tổng số chuỗi con của chuỗi có n ký tự là n * (n + 1) / 2.
Bây giờ chúng ta sẽ duyệt qua chuỗi và cho từng loại ký tự ‘a’, ‘b’ hoặc ‘c’. Chúng tôi sẽ kiểm tra các chỉ mục trước đó của hai ký tự còn lại (‘b’, ’c’), (‘c’, ’a’) và (‘a’, ‘b’). Chỉ cần trừ đi chỉ số tối thiểu của hai chỉ số còn lại vì chúng ta biết rằng chúng ta đang xóa ký tự đó để bao gồm ký tự hiện tại trong chuỗi con để nó không chứa cả ba.
-
Lấy một chuỗi str dưới dạng một mảng ký tự.
-
Hàm sub_without_all (char str [], int size) nhận một chuỗi, nó có độ dài và trả về số lượng các chuỗi con không chứa tất cả ‘a’, ‘b’ và ‘c’.
-
Lấy kích thước đếm ban đầu * (size + 1) / 2 cho số tất cả các chuỗi con có thể có của str [].
-
Lấy các biến a, b, c để lưu chỉ số cuối cùng của ‘a’, ‘b’, ‘c’ trong str []. Khởi tạo tất cả bằng 0.
-
Traverse str [] bằng cách sử dụng vòng lặp for từ i =0 đến i
-
Nếu str [i] ==’a’ cập nhật chỉ số của ‘a’ là a =i + 1. Trừ chỉ số tối thiểu của ‘b’ hoặc ‘c’ khỏi số đếm để bao gồm ‘a’ trong chuỗi con. Trừ b, c cho số nào nhỏ nhất khỏi số đếm.
-
Làm tương tự như bước trước cho str [i] ==’b’ hoặc str [i] ==’c’.
-
Cuối cùng, chúng tôi được tính là chuỗi con của str [] mà không có cả ba ký tự trong chúng cùng một lúc.
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15