Leetcode 1358 Number of Substrings Containing All Three Characters

In this Leetcode problem, we are asked to count all the substrings containing a, b and c given a String as input. Here is the exact wording:

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.

Problem statement with some test cases:

Problem statement

Solution

The algorithm we are going to use is a sliding window and counting the number of occurrences of each character in the sliding window.

Algorithm

• We maintain a sliding window with 2 pointers start and end, the sliding window is [start, end[.
• If all chars are present in the sliding window, it means, all the substrings substring(start, end), substring(start, end + 1), …, substring(start, n) are valid substrings. we add n — end + 1 to the number of substrings and move start to the right (and update counter)
• if not all chars are present, we move end to the right (and update counter)
• We do so until start reaches n or (end reaches n and we don’t have all chars)

Implementation