推 Meaverzt: 大師 03/12 00:34
→ Meaverzt: 我直接用昨天的改結果一坨 03/12 00:34
https://leetcode.com/problems/number-of-substrings-containing-all-three-characters
1358. Number of Substrings Containing All Three Characters
給你一個包含abc的字串，找出至少有一個a、b、c的所有子字串數量。
思路:
1.類似昨天那題用鴿籠原理去想，正攻法我破頭想不太出來，全部子陣列數量=1+2+3+...
+n，找出所有不包含a,b,c其中一個的子字串數量，然後用全部的數量去減只有一種和
只有兩種的，至少我是覺得這樣比較好想= =。
Java Code:
----------------------------------------------------
class Solution {
public int numberOfSubstrings(String s) {
int n = s.length();
long all = (long) (n + 1) * n / 2;
int lessThree = 0;
int l = 0;
int[] cnt = new int[3];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
while (count(cnt) > 2) {
cnt[s.charAt(l++) - 'a']--;
}
lessThree += (i - l + 1);
}
return (int) (all - lessThree);
}
int count(int[] cnt) {
return (cnt[0] > 0 ? 1 : 0) + (cnt[1] > 0 ? 1: 0) + (cnt[2] > 0 ? 1 :
0);
}
}
----------------------------------------------------
--
https://i.imgur.com/yRXNquY.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1741710571.A.39A.html
※ 編輯: Rushia (49.158.101.161 臺灣), 03/12/2025 00:30:35