Giả sử chúng ta đã cho một chuỗi s chỉ gồm các ký tự a, b và c. Chúng ta phải trả về số chuỗi con chứa ít nhất một lần xuất hiện của tất cả các ký tự a, b và c này. Vì vậy, ví dụ:nếu chuỗi là “abcabc”, thì đầu ra sẽ là 10, vì chuỗi con chứa ít nhất một lần xuất hiện của các ký tự a, b và c, chúng là “abc”, “abca”, “abcab”, “Abcabc”, “bca”, “bcab”, “cab”, “cabc” và “abc” (một lần nữa cho phần cuối cùng).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ret:=0, tạo bản đồ có tên m, đặt j:=0
-
cho tôi trong phạm vi từ 0 đến kích thước của s
-
tăng số lượng s [i] trong bản đồ m
-
trong khi m [‘a’]> 0 và m [‘b’]> 0 và m [‘c’]> 0,
-
giảm số lượng s [i] trong bản đồ m
-
tăng j lên 1
-
-
tăng ret lên j
-
-
trả lại ret
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numberOfSubstrings(string s) {
int ret = 0;
map <char, int> m;
int j = 0;
for(int i = 0; i < s.size(); i++){
m[s[i]]++;
while(m['a'] > 0 && m['b'] > 0 && m['c'] > 0){
m[s[j]]--;
j++;
}
ret += j;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numberOfSubstrings("abcabc"));
} Đầu vào
"abcabc"
Đầu ra
10