1358. Number of Substrings Containing All Three Characters - Detailed Explanation

Problem Statement

Given a string s consisting only of the characters 'a', 'b', and 'c', the goal is to find the number of substrings that contain at least one occurrence of all three characters. A substring is a contiguous sequence of characters within s.

Example 1

• Input: s = "abc"
• Output: 1
• Explanation: The only substring that contains 'a', 'b', and 'c' is "abc" itself.

Example 2

• Input: s = "aaabc"
• Output: 3
• Explanation: The substrings "aaabc", "aabc", and "abc" each contain at least one 'a', 'b', and 'c'.

Example 3

• Input: s = "abcabc"
• Output: 10
• Explanation: There are 10 substrings that include at least one of each character.

Constraints:

• The string s consists only of 'a', 'b', and 'c'.
• The length of s can be large, so an efficient solution is required.

Hints

1. Sliding Window Technique:
   Use a two-pointer (or sliding window) approach to maintain a window that contains all three characters. For each valid window, determine how many substrings ending beyond the window contribute to the answer.

2. Counting Valid Substrings:
   When a window from index i to j is valid (i.e., it contains at least one 'a', 'b', and 'c'), every substring starting at i and ending at any index from j to the end of the string will be valid. Thus, you can add (n - j) to the answer where n is the length of the string.

3. Optimized Window Movement:
   Use a frequency array or dictionary to keep track of the count of 'a', 'b', and 'c' in the current window. Expand the window until it becomes valid, then shrink it from the left to count all valid substrings starting at that position.

Approach

Sliding Window with Two Pointers

1. Initialization:

   • Use two pointers, i (left) and j (right), both starting at 0.
   • Maintain a frequency counter for 'a', 'b', and 'c'.

2. Expand the Window:

   • Move the right pointer j until the window [i, j] contains at least one occurrence of all three characters.

3. Count Valid Substrings:

   • Once the window is valid, every substring starting at i and ending from j to the end of s is valid. Add (n - j) to the answer.

4. Shrink the Window:

   • Increment the left pointer i to try a new starting position, and update the frequency counter accordingly.
   • Continue this process until you have traversed the entire string.

5. Result:

   • The total count accumulated gives the number of substrings containing at least one 'a', 'b', and 'c'.

Complexity Analysis

• Time Complexity: O(n)
  Each character is processed at most twice (once when expanding the window and once when shrinking it).

• Space Complexity: O(1)
  Only a fixed-size frequency counter for 3 characters is used.

Python Code

Java Code

Step-by-Step Walkthrough and Visual Examples

1. Initialization:
   For a given string s of length n, start with both pointers i and j at index 0 and initialize a frequency counter for 'a', 'b', and 'c' all to 0.

2. Expanding the Window:

   • Move the right pointer j until the substring s[i...j-1] includes at least one of each character.
   • For example, for s = "abcabc" and i = 0, increment j until j == 3 where substring "abc" is valid.

3. Counting Valid Substrings:

   • Once the window is valid (e.g., "abc" from index 0 to 2), all substrings starting at index 0 and ending from j to n - 1 are valid.
   • Add (n - j) to the answer. In the example, if n = 6 and j = 3, add 3 valid substrings.

4. Shrinking the Window:

   • Move the left pointer i to the right by one and update the frequency counter by decrementing the count of the character leaving the window.
   • Continue this process for all possible starting indices i.

5. Final Result:
   The accumulated count is the total number of substrings that contain at least one 'a', 'b', and 'c'.

Common Mistakes

• Forgetting to Shrink the Window:
  Not decrementing the frequency counter when the left pointer moves can lead to over-counting.

• Incorrect Condition for Validity:
  Ensure that the window is only considered valid when all three characters have a count of at least one.

• Off-by-One Errors:
  Be cautious with index adjustments when calculating the number of valid substrings.

Edge Cases

• Minimal String:
  When the string is "abc", there is only one valid substring.

• No Valid Substring:
  If the string does not contain all three characters, the output should be 0.

• Repeated Characters:
  Strings with many repeated characters require careful management of the frequency counts.

Alternative Variations

• Counting Substrings with At Least k Occurrences:
  Instead of at least one occurrence of each character, you might be asked for at least k occurrences.

• Different Sets of Characters:
  The problem can be generalized to any set of characters, not just 'a', 'b', and 'c'.

Related Problems

• Remove All Occurrences of a Substring

• Count Vowel Substrings of a String

• Count Subarrays With Fixed Bounds