A string is good if there are no repeated characters.
Given a string s
, return the number of good substrings of length three in s
.
Note that if there are multiple occurrences of the same substring, every occurrence should be counted.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "xyzzaz" Output: 1 Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". The only good substring of length 3 is "xyz".
Example 2:
Input: s = "aababcabc" Output: 4 Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc". The good substrings are "abc", "bca", "cab", and "abc".
Constraints:
1 <= s.length <= 100
s
consists of lowercase English letters.
Solution: Brute Force w/ (Hash)Set
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 |
class Solution { public: int countGoodSubstrings(string s) { int ans = 0; for (int i = 0; i + 2 < s.length(); ++i) ans += set<char>(s.begin() + i, s.begin() + i + 3).size() == 3; return ans; } }; |
Python3
1 2 3 |
class Solution: def countGoodSubstrings(self, s: str) -> int: return sum(len(set(s[i:i + 3])) == 3 for i in range(len(s) - 2)) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment