สมมติว่าเราให้สตริง s ที่ประกอบด้วยอักขระ a, b และ c เท่านั้น เราต้องคืนค่าจำนวนสตริงย่อยที่มีอักขระ a, b และ c ทั้งหมดเกิดขึ้นอย่างน้อยหนึ่งครั้ง ตัวอย่างเช่น หากสตริงคือ "abcabc" ผลลัพธ์จะเป็น 10 เนื่องจากสตริงย่อยที่มีอักขระ a, b และ c เกิดขึ้นอย่างน้อยหนึ่งตัว ได้แก่ "abc", "abca", "abcab", “abcabc”, “bca”, “bcab”, “cab”, “cabc” และ “abc” (อีกครั้งสำหรับส่วนสุดท้าย)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0 สร้างแผนที่ชื่อ m ตั้งค่า j :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ s
-
เพิ่มจำนวน s[i] ในแผนที่ m
-
ในขณะที่ m['a']> 0 และ m['b']> 0 และ m['c']> 0
-
ลดจำนวน s[i] ในแผนที่ m
-
เพิ่มขึ้น 1
-
-
เพิ่ม ret โดย j
-
-
รีเทิร์น
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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"));
} อินพุต
"abcabc"
ผลลัพธ์
10
