Coding

Number of Equal Count Substrings

Asked at

Expedia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a 0-indexed string s consisting of only lowercase English letters, and an integer count. A substring of s is said to be an equal count substring if, for each unique letter in the substring, it appears exactly count times in the substring.

Return the number of equal count substrings in s.

A substring is a contiguous non-empty sequence of characters within a string.

Input: s = "aaabcbbcc", count = 3 Output: 3 Explanation: The substring that starts at index 0 and ends at index 2 is "aaa". The letter 'a' in the substring appears exactly 3 times. The substring that starts at index 3 and ends at index 8 is "bcbbcc". The letters 'b' and 'c' in the substring appear exactly 3 times. The substring that starts at index 0 and ends at index 8 is "aaabcbbcc". The letters 'a', 'b', and 'c' in the substring appear exactly 3 times.

Input: s = "abcd", count = 2 Output: 0 Explanation: The number of times each letter appears in s is less than count. Therefore, no substrings in s are equal count substrings, so return 0.

Consider the string s = "aabbbcccc" and count = 2. How many equal count substrings exist?

1 <= s.length <= 3 * 104
1 <= count <= 3 * 104
s consists only of lowercase English letters.

cpp

class Solution {
public:
    int equalCountSubstrings(string s, int count) {
        // Your code goes here
    }
};

java

class Solution {
    public int equalCountSubstrings(String s, int count) {
        // Your code goes here
    }
}

python

class Solution:
    def equalCountSubstrings(self, s: str, count: int) -> int:
        # Your code goes here

javascript

class Solution {
    equalCountSubstrings(s, count) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public int EqualCountSubstrings(string s, int count)
    {
        // Your code goes here
    }
}

func equalCountSubstrings(s string, count int) int {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Enumerate possible distinct-letter counts from one to 26.
02Set window length to distinctCount times count.
03Slide a fixed-size window.
04Track how many characters occur exactly count times.
05Count windows where all present characters qualify.

Reference answer

An equal-count substring with d distinct letters has fixed length d * count, and lowercase input gives only 26 possible values of d. For each d from 1 to 26 with feasible length, slide a window of exactly that length. Maintain a frequency array and a counter good for letters whose frequency is exactly count; update it carefully when a character enters or leaves by removing its old contribution before changing the count and adding its new contribution after. The window is valid exactly when good == d, because its length already forces no additional positive-frequency letters. This costs O(26*N) time and O(26) space, which is linear for a fixed alphabet. It avoids a quadratic substring enumeration.

Then expect these follow-ups

How does a large arbitrary alphabet change this?
Tests: constraints
Can you return the matching windows?
Tests: index tracking

Hiring now

Expedia has 109 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Development Engineer III - Platform Productivity Tools
India - Gurgaon
Sr Manager, Software Engineering
Austin Domain 11 - HomeAway
Software Development Engineer II
India - Gurgaon

Or practice this question first

Next question