Number of Substrings Containing All Three Characters

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.

def number_of_substrings(s: str) -> int:
    """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.
    """
    n = len(s)
    count = 0
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            if 'a' in sub and 'b' in sub and 'c' in sub:
                count += 1
    return count

# Example usage
s = "abcabc"
print(number_of_substrings(s))

s = "aaacb"
print(number_of_substrings(s))

s = "abc"
print(number_of_substrings(s))


# Optimal solution using sliding window
def number_of_substrings_optimal(s: str) -> int:
    n = len(s)
    count = 0
    left = 0
    freq = {'a': 0, 'b': 0, 'c': 0}
    for right in range(n):
        freq[s[right]] += 1
        while freq['a'] > 0 and freq['b'] > 0 and freq['c'] > 0:
            count += n - right
            freq[s[left]] -= 1
            left += 1
    return count

# Example usage
s = "abcabc"
print(number_of_substrings_optimal(s))

s = "aaacb"
print(number_of_substrings_optimal(s))

s = "abc"
print(number_of_substrings_optimal(s))

Brute Force Solution

The brute force solution iterates through all possible substrings of the input string s and checks if each substring contains at least one occurrence of characters 'a', 'b', and 'c'. If a substring satisfies this condition, the count is incremented. The final count represents the number of substrings that meet the criteria.

Optimal Solution

The optimal solution uses a sliding window approach to efficiently count the substrings. It maintains a window defined by left and right pointers. The window expands to the right, and the frequency of characters within the window is tracked using a dictionary freq. Once the window contains at least one occurrence of each character ('a', 'b', and 'c'), the algorithm increments the count by the number of substrings that can be formed by extending the window to the end of the string (n - right). Then, the window shrinks from the left until one of the characters is no longer present in the window, ensuring that the window always contains the minimum required characters. This process continues until the right pointer reaches the end of the string.

Big(O) Run-time Analysis

• Brute Force Solution: O(n^3), where n is the length of the string. The nested loops iterate through all possible substrings, and the in operator within the inner loop takes O(n) time in the worst case.
• Optimal Solution: O(n), where n is the length of the string. The right pointer iterates through the string once, and the left pointer also iterates through the string at most once. The operations inside the loops take constant time.

Big(O) Space Usage Analysis

• Brute Force Solution: O(1). The space used is constant because we are only using a few variables to store the count and the substring.
• Optimal Solution: O(1). The space used is constant because the freq dictionary always contains at most three key-value pairs ('a', 'b', and 'c').

Edge Cases

• Empty String: If the input string is empty, the function should return 0.
• String with Length Less Than 3: If the length of the input string is less than 3, and it doesn't contain all three characters, the function should return 0.
• String with Repeated Characters: The function should correctly handle strings with repeated characters, such as "aaabc", "aabbc", or "abccc".
• String with Characters Other Than 'a', 'b', and 'c': According to problem statement the string will only have a,b,c chars so validation is not needed, but it could be added for robustness.