1358. Number of Substrings Containing All Three Characters LeetCode Solution
In this guide, you will get 1358. Number of Substrings Containing All Three Characters LeetCode Solution with the best time and space complexity. The solution to Number of Substrings Containing All Three Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Substrings Containing All Three Characters
Given a string s consisting only of characters a, b and c.
Return the number of substrings containing at least one occurrence of all these characters a, b and c.
Example 1:
Input: s = “abcabc”
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” and “abc” (again).
Example 2:
Input: s = “aaacb”
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “aaacb”, “aacb” and “acb”.
Example 3:
Input: s = “abc”
Output: 1
Constraints:
3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(3) = O(1)
1358. Number of Substrings Containing All Three Characters LeetCode Solution in C++
class Solution {
public:
// Similar to 3. Longest Substring Without Repeating Characters
int numberOfSubstrings(string s) {
int ans = 0;
vector<int> count(3);
int l = 0;
for (const char c : s) {
++count[c - 'a'];
while (count[0] > 0 && count[1] > 0 && count[2] > 0)
--count[s[l++] - 'a'];
// s[0..r], s[1..r], ..., s[l - 1..r] are satified strings.
ans += l;
}
return ans;
}
}; /* code provided by PROGIEZ */
1358. Number of Substrings Containing All Three Characters LeetCode Solution in Java
class Solution {
// Similar to 3. Longest SubString Without Repeating Characters
public int numberOfSubstrings(String s) {
int ans = 0;
int[] count = new int[3];
int l = 0;
for (final char c : s.toCharArray()) {
++count[c - 'a'];
while (count[0] > 0 && count[1] > 0 && count[2] > 0)
--count[s.charAt(l++) - 'a'];
// s[0..r], s[1..r], ..., s[l - 1..r] are satified strings.
ans += l;
}
return ans;
}
} // code provided by PROGIEZ
1358. Number of Substrings Containing All Three Characters LeetCode Solution in Python
class Solution:
# Similar to 3. Longest SubWithout Repeating Characters
def numberOfSubstrings(self, s: str) -> int:
ans = 0
count = {c: 0 for c in 'abc'}
l = 0
for c in s:
count[c] += 1
while min(count.values()) > 0:
count[s[l]] -= 1
l += 1
# s[0..r], s[1..r], ..., s[l - 1..r] are satified strings.
ans += l
return ans # code by PROGIEZ
