Solution Explanation:

This problem asks to find the number of substrings in a given string that contain at least one occurrence of each of the characters 'a', 'b', and 'c'. The optimal solution uses a sliding window approach enhanced with a clever tracking mechanism.

Approach: Sliding Window with Efficient Character Tracking

Instead of generating all possible substrings and checking each one, we utilize a sliding window that expands and contracts as we traverse the string. The key is efficiently tracking which characters are currently present within the window. We avoid redundant checks by keeping track of the last seen index of each character ('a', 'b', 'c').

1. Initialization: We initialize an array d (or a hash map) to store the last seen index of each character. The initial values are -1, indicating that none of the characters have been encountered yet. We also initialize a counter ans to 0, which will store the count of valid substrings.

2. Iteration: We iterate through the string s using a single loop.

3. Update Last Seen Index: For each character c at index i, we update its last seen index d[c - 'a'] to i.

4. Check for Validity: The crucial part is determining whether the current window contains all three characters. The minimum of the last seen indices in d (min(d[0], d[1], d[2])) represents the index of the rightmost character whose last occurrence is furthest to the left. Any substring starting before that index would lack at least one of the characters ('a','b','c'). This implies that all substrings ending at i and starting at min(d[0], d[1], d[2]) + 1 or later will have at least one of each character. Therefore, we add min(d[0], d[1], d[2]) + 1 to the count ans.

5. Return Count: Finally, we return the total count ans.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the string. We iterate through the string only once. The operations within the loop (updates and comparisons) are constant time.

• Space Complexity: O(1). We use a fixed-size array d to store the last seen indices of the three characters, regardless of the input string's length.

Code Implementation (Python):

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

Code Implementation (Java):

class Solution {
    public int numberOfSubstrings(String s) {
        int[] d = new int[]{-1, -1, -1}; //Use array for efficiency
        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 Implementation (C++):

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

Code Implementation (Go):

func numberOfSubstrings(s string) int {
	d := [3]int{-1, -1, -1} // Use array for efficiency
	ans := 0
	for i, c := range s {
		d[c-'a'] = i
		ans += min(min(d[0],d[1]),d[2]) + 1
	}
	return ans
}
 
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The code in all languages demonstrates the same efficient single-pass algorithm, achieving linear time complexity. The choice of using an array d or a hashmap is largely a matter of style and language preference; in this case, an array is slightly more efficient due to direct indexing.