1358. Number of Substrings Containing All Three Characters Medium

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

Approach

Input: A string s containing only the characters 'a', 'b', and 'c'

Output: Return the total number of substrings where 'a', 'b', and 'c' each appear at least once.

This problem operates using the Variable-length Sliding Window technique.

We need to use a frequency map to monitor the occurrence count of 'a', 'b', and 'c' within our current sliding window.

Taking the left boundary as our starting point, we advance the right boundary traversing forwards. With every extension on the right side, we proportionally update our map array to denote character frequencies observed.

When the state meets our stipulated condition (i.e. 'a'>0, 'b'>0, 'c'>0), it serves as an indicator that the current substring block satisfies all conditions. More crucially, any further character additions expanding rightwards will still preserve the required constraints. Hence, we can update our calculation mathematically: ans += len(s) - right.

After evaluating the sequence, we contract the window bounds by moving the left pointer successively towards the right side until the compliance requirements falter, after which we go back to pushing the right boundary to reestablish viability logic on new sliding intervals.

The primary difficulty here centers on grasping the mathematical correlation property: upon validating a window bounded locally, all subsequent longer substrings ending beyond right invariably integrate the requisite values successfully. Thus we can tally them rapidly utilizing ans += len(s) - right.

Implementation

python

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        left = 0               # Trailing sliding window edge position
        ans = 0                # Numerical counter representing identified conforming subsets
        countMap = { 'a': 0, 'b': 0, 'c': 0 }  # Tally monitoring observed counts mapped against targets

        # Iterate examining char values stretching bound string lengths assigning parameters respectively
        for right in range(len(s)):
            # Record observation metrics 
            countMap[s[right]] += 1

            # Threshold confirmation checks matching all values exceeding base parameter limits at minimum once 
            while countMap['a'] > 0 and countMap['b'] > 0 and countMap['c'] > 0:
                # Represents condition validating entire blocks stretched behind 'right' index till physical limits termination. 
                # Validated sequences natively scale outwards preserving core condition bounds inherently 
                ans += len(s) - right

                # Iteratively truncate front edges releasing limits pushing pointer values forward testing threshold strength
                countMap[s[left]] -= 1
                left += 1  # Drag boundary rightward 

        return ans

javascript

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function(s) {
    const map = { a: 0, b: 0, c: 0 };

    let left = 0;
    let ans = 0;

    for (let right = 0; right < s.length; right++) {
        map[s[right]]++;

        while (map['a'] > 0 && map['b'] > 0 && map['c'] > 0) {
            ans += s.length - right;
            map[s[left]]--;
            left++;
        }
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1) minimum constraints for object map allocation

Links

1358. Number of Substrings Containing All Three Characters (English)1358. 包含所有三种字符的子字符串数目 (Chinese)