Count Complete Substrings

Count Complete Substrings

What is this problem about?

The Count Complete Substrings interview question is a "Hard" string problem. A substring is "complete" if:

1. Every character in the substring appears exactly k times.
2. The absolute difference between the values of every two adjacent characters in the substring is at most 2.

Why is this asked in interviews?

Meesho asks this Sliding Window interview pattern to test your ability to decompose a problem with multiple orthogonal constraints. It evaluates if you can split the string into segments where the second condition (adjacent difference) holds, and then solve the "exactly k times" problem on each segment using a fixed-size sliding window.

Algorithmic pattern used

The problem uses Divide and Conquer with Sliding Window.

1. Segmenting: Split the string into blocks where every adjacent pair has a difference <= 2.
2. Counting: For each block, we need to find substrings where each char appears k times.
3. If there are m distinct characters in a complete substring, its length must be m * k.
4. Since there are at most 26 distinct lowercase letters, we can iterate through all possible values of m (1 to 26).
5. For a fixed m, we use a sliding window of fixed size m * k and check if all characters in the window appear exactly k times.

Example explanation

s = "igigee", k = 2

1. 'i' and 'g' difference is 2. 'g' and 'i' is 2... All adjacent pairs are valid. One block: "igigee".
2. Try m=1 (length 2): ig, gi, ig, ge, ee. Only "ee" has all chars appearing 2 times.
3. Try m=2 (length 4): igig, gige, igee. Only "igig" is valid.
4. Try m=3 (length 6): "igigee". Chars: i:2, g:2, e:2. Valid! Total count: 3.

Common mistakes candidates make

• O(N^2) search: Checking every substring manually, which is too slow.
• Ignoring adjacent rule: Forgetting to split the string into blocks first, which makes the frequency counting much harder.
• Window size: Not realizing that the length of a "complete" substring must be a multiple of k.

Interview preparation tip

When a problem has a constraint like "each character appears exactly k times," the search space for the length of the substring is limited to 1*k, 2*k, ..., 26*k. This is a huge optimization!