LeetCode 1358. Number of Substrings Containing All Three Characters Solution in Java, C++, Python & Go | Explanation + Code

Description

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.

Solutions

Solution 1: Single Pass

We use an array d of length 3 to record the most recent occurrence of the three characters, initially all set to -1.

We traverse the string s. For the current position i, we first update d[s[i]]=i, then the number of valid strings is min(d[0], d[1], d[2]) + 1, which is accumulated to the answer.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

PythonJavaC++Go

class Solution: def numberOfSubstrings(self, s: str) -> int: d = {"a": -1, "b": -1, "c": -1} ans = 0 for i, c in enumerate(s): d[c] = i ans += min(d["a"], d["b"], d["c"]) + 1 return ans(code-box)

class Solution { public int numberOfSubstrings(String s) { int[] d = new int[] {-1, -1, -1}; int ans = 0; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); d[c - 'a'] = i; ans += Math.min(d[0], Math.min(d[1], d[2])) + 1; } return ans; } }(code-box)

class Solution { public: int numberOfSubstrings(string s) { int d[3] = {-1, -1, -1}; int ans = 0; for (int i = 0; i < s.size(); ++i) { d[s[i] - 'a'] = i; ans += min(d[0], min(d[1], d[2])) + 1; } return ans; } };(code-box)

func numberOfSubstrings(s string) (ans int) { d := [3]int{-1, -1, -1} for i, c := range s { d[c-'a'] = i ans += min(d[0], min(d[1], d[2])) + 1 } return }(code-box)