Problem Description

You are given a string s that contains only three types of characters: 'a', 'b', and 'c'.

Your task is to count how many substrings of s contain at least one occurrence of each of the three characters ('a', 'b', and 'c').

A substring is a contiguous sequence of characters within the string. For example, if s = "abcabc", then "abc", "abca", "bcab", "abcabc" are all valid substrings that contain at least one 'a', one 'b', and one 'c'.

The key insight in the solution is tracking the most recent position of each character as we iterate through the string. For each position i, we maintain the latest occurrence index of 'a', 'b', and 'c' in a dictionary d.

At each position, after updating the current character's position, the number of valid substrings ending at position i equals min(d["a"], d["b"], d["c"]) + 1. This works because:

• The minimum value among the three positions tells us the rightmost position where all three characters have appeared at least once
• Any substring starting from position 0 up to this minimum position (inclusive) and ending at the current position i will contain all three characters
• That's why we add min(d["a"], d["b"], d["c"]) + 1 to our answer (the +1 accounts for 0-indexing)

For example, if at position 5 we have d = {"a": 2, "b": 4, "c": 1}, then min(2, 4, 1) + 1 = 2, meaning there are 2 valid substrings ending at position 5 that contain all three characters.

Intuition

The challenge here is to efficiently count all substrings that contain at least one of each character 'a', 'b', and 'c'. A brute force approach would check every possible substring, but that would be inefficient with O(n²) or O(n³) complexity.

Let's think about this problem differently. For any position i in the string, we want to know: how many substrings ending at position i contain all three characters?

The key observation is that if we know the most recent positions where each character appeared, we can determine all valid substrings ending at the current position. Why? Because once we have seen all three characters at least once, any substring that:

• Ends at the current position i
• Starts at or before the position where the "last to appear" character showed up

will definitely contain all three characters.

Consider this example: if we're at position 7 and we last saw 'a' at position 5, 'b' at position 3, and 'c' at position 6, then the "last to appear" among the three was at position 3 (the minimum). This means:

• Any substring from position 0 to 7 contains all three characters
• Any substring from position 1 to 7 contains all three characters
• Any substring from position 2 to 7 contains all three characters
• Any substring from position 3 to 7 contains all three characters
• But substrings starting after position 3 won't contain 'b'

So we have exactly min(5, 3, 6) + 1 = 4 valid substrings ending at position 7.

This leads us to the elegant solution: maintain the most recent position of each character, and for each position in our traversal, add min(last_position_of_a, last_position_of_b, last_position_of_c) + 1 to our answer. The +1 accounts for zero-indexing - if the minimum position is 0, we have 1 valid substring; if it's 1, we have 2 valid substrings, and so on.

Learn more about Sliding Window patterns.

Solution Approach

The implementation uses a single-pass algorithm with a dictionary to track the most recent positions of each character.

Data Structure:

• We use a dictionary d with three keys: "a", "b", and "c", all initialized to -1. The value -1 indicates that the character hasn't been encountered yet.

Algorithm Steps:

1. Initialize the dictionary d = {"a": -1, "b": -1, "c": -1} and answer counter ans = 0.

2. Iterate through the string using enumerate(s) to get both the index i and character c at each position.

3. For each character at position i:

   • Update the dictionary: d[c] = i to record the most recent position of character c
   • Calculate the number of valid substrings ending at position i: min(d["a"], d["b"], d["c"]) + 1
   • Add this count to the answer: ans += min(d["a"], d["b"], d["c"]) + 1

4. Return the total count ans.

Why this works:

• When min(d["a"], d["b"], d["c"]) returns -1, it means at least one character hasn't appeared yet, so (-1) + 1 = 0 valid substrings.
• When all three characters have appeared at least once, min(d["a"], d["b"], d["c"]) gives us the leftmost position where we can start a substring that includes all three characters when ending at the current position.
• The +1 converts from the position index to the count of valid starting positions (positions 0 through the minimum position, inclusive).

Time Complexity: O(n) where n is the length of the string, as we make a single pass through the string.

Space Complexity: O(1) as we only use a fixed-size dictionary with 3 entries regardless of input size.

Example Walkthrough

Let's walk through the solution with s = "abcabc".

We'll track the most recent position of each character in dictionary d and count valid substrings at each step.

Initial state:

• d = {"a": -1, "b": -1, "c": -1}
• ans = 0

Position 0: s[0] = 'a'

• Update: d["a"] = 0, so d = {"a": 0, "b": -1, "c": -1}
• Calculate: min(0, -1, -1) + 1 = -1 + 1 = 0
• No valid substrings yet (missing 'b' and 'c')
• ans = 0

Position 1: s[1] = 'b'

• Update: d["b"] = 1, so d = {"a": 0, "b": 1, "c": -1}
• Calculate: min(0, 1, -1) + 1 = -1 + 1 = 0
• No valid substrings yet (missing 'c')
• ans = 0

Position 2: s[2] = 'c'

• Update: d["c"] = 2, so d = {"a": 0, "b": 1, "c": 2}
• Calculate: min(0, 1, 2) + 1 = 0 + 1 = 1
• Valid substring: "abc" (starting at position 0, ending at position 2)
• ans = 0 + 1 = 1

Position 3: s[3] = 'a'

• Update: d["a"] = 3, so d = {"a": 3, "b": 1, "c": 2}
• Calculate: min(3, 1, 2) + 1 = 1 + 1 = 2
• Valid substrings ending at position 3:
  • "abca" (starting at position 0)
  • "bca" (starting at position 1)
• ans = 1 + 2 = 3

Position 4: s[4] = 'b'

• Update: d["b"] = 4, so d = {"a": 3, "b": 4, "c": 2}
• Calculate: min(3, 4, 2) + 1 = 2 + 1 = 3
• Valid substrings ending at position 4:
  • "abcab" (starting at position 0)
  • "bcab" (starting at position 1)
  • "cab" (starting at position 2)
• ans = 3 + 3 = 6

Position 5: s[5] = 'c'

• Update: d["c"] = 5, so d = {"a": 3, "b": 4, "c": 5}
• Calculate: min(3, 4, 5) + 1 = 3 + 1 = 4
• Valid substrings ending at position 5:
  • "abcabc" (starting at position 0)
  • "bcabc" (starting at position 1)
  • "cabc" (starting at position 2)
  • "abc" (starting at position 3)
• ans = 6 + 4 = 10

Final Answer: 10

The algorithm correctly identifies that there are 10 substrings containing at least one of each character 'a', 'b', and 'c'.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string once using enumerate, and for each character, it performs constant-time operations: updating the dictionary with the current index and calculating the minimum of three values. Since we traverse the string exactly once with O(1) operations per iteration, the overall time complexity is linear.

The space complexity is O(1). The algorithm uses a fixed-size dictionary d that always contains exactly 3 key-value pairs (for characters 'a', 'b', and 'c'), regardless of the input size. The only other variables are the counter ans and the loop variables i and c, all of which use constant space. Therefore, the space usage does not grow with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization Value

A common mistake is initializing the dictionary with 0 instead of -1:

# Wrong
last_seen_index = {"a": 0, "b": 0, "c": 0}

Why it's wrong: When characters haven't appeared yet, using 0 would incorrectly suggest they appeared at position 0. This leads to counting invalid substrings that don't actually contain all three characters.

Solution: Always initialize with -1 to clearly indicate "not seen yet":

# Correct
last_seen_index = {"a": -1, "b": -1, "c": -1}

2. Off-by-One Error in Counting

Forgetting to add 1 when calculating valid substrings:

# Wrong
total_count += min_index  # Missing the +1

Why it's wrong: The minimum index represents a position (0-based), but we need the count of valid starting positions. For example, if min_index = 2, there are actually 3 valid starting positions: 0, 1, and 2.

Solution: Always add 1 to convert from index to count:

# Correct
total_count += min_index + 1

3. Using Wrong Data Structure

Attempting to use a list or array instead of a dictionary:

# Wrong approach
last_seen = [-1, -1, -1]  # for 'a', 'b', 'c'
# Then trying to map characters to indices manually

Why it's problematic: This requires additional logic to map characters to array indices (like ord(char) - ord('a')), making the code more error-prone and less readable.

Solution: Use a dictionary for clear, self-documenting code:

# Correct
last_seen_index = {"a": -1, "b": -1, "c": -1}
last_seen_index[char] = current_index  # Direct and clear

4. Misunderstanding the Algorithm Logic

Trying to count substrings starting at the current position instead of ending at it:

# Wrong interpretation
for i in range(len(s)):
    # Trying to find valid substrings starting from position i
    # This requires checking forward, making the solution O(n²)

Why it's wrong: This fundamentally changes the algorithm and typically results in O(n²) complexity instead of the optimal O(n).

Solution: Focus on counting substrings that end at each position, using the minimum of the last seen positions to determine how many valid starting positions exist.