Số Lượng Chuỗi Con Chứa Tất Cả Ba Ký Tự Trong C++

Giả sử chuỗi s chỉ chứa ký tự a, b, c. Trả về số lượng chuỗi con chứa ít nhất một lần xuất hiện của cả ba ký tự a, b, c. Ví dụ: "abcabc" → 10. Các chuỗi con: "abc", "abca", "abcab", "abcabc", "bca", "bcab", "cab", "cabc", "abc" (lần 2).

Để giải quyết, chúng ta làm theo các bước:

• ret = 0, map m, j = 0.

• Với i từ 0 đến độ dài s: tăng m[s[i]]; khi m['a']>0 và m['b']>0 và m['c']>0: giảm m[s[j]]; j++; ret += j.

• Trả về ret.

Ví dụ (C++)

Hãy xem 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;
    }
};

int main(){
    Solution ob;
    cout << (ob.numberOfSubstrings("abcabc"));
}

Đầu vào

"abcabc"

Đầu ra

10