Skip to main content
Talentd

Count Complete Substrings - Solution & Explanation

HardHash TableStringSliding Window18 min readAsked at: Meesho
Practice this problem

Problem Statement

You are given a string word and an integer k.

A substring s of word is complete if:

  • Each character in s occurs exactly k times.
  • The difference between two adjacent characters is at most 2. That is, for any two adjacent characters c1 and c2 in s, the absolute difference in their positions in the alphabet is at most 2.

Return the number of complete substrings of word.

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

 

Example 1:

Input: word = "igigee", k = 2
Output: 3
Explanation: The complete substrings where each character appears exactly twice and the difference between adjacent characters is at most 2 are: igigee, igigee, igigee.

Example 2:

Input: word = "aaabbbccc", k = 3
Output: 6
Explanation: The complete substrings where each character appears exactly three times and the difference between adjacent characters is at most 2 are: aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc.

 

Constraints:

  • 1 <= word.length <= 105
  • word consists only of lowercase English letters.
  • 1 <= k <= word.length

Approach Overview

Problem Overview: Given a string word and an integer k, count substrings where every distinct character appears exactly k times and the absolute difference between adjacent characters is at most 2. The substring must satisfy both constraints simultaneously, which means you must carefully control character frequency while maintaining a valid character range.

Approach 1: Brute Force Substring Validation (O(n2 * 26) time, O(26) space)

Generate every possible substring starting at index i and expand it to the right. Maintain a frequency map for characters as the substring grows. At each step, verify two conditions: the difference between the current and previous character is ā‰¤ 2, and every character in the substring appears exactly k times. Because a substring can contain at most 26 lowercase letters, validating frequencies takes constant time. This approach works for small inputs and is useful to confirm correctness, but scanning all substrings leads to quadratic growth.

Approach 2: Sliding Window with Frequency Map (O(26 * n) time, O(26) space)

The key observation: if every character appears exactly k times, the substring length must be distinct * k. Iterate over possible numbers of distinct characters from 1 to 26. For each target count, use a fixed-length sliding window of size distinct * k. Track character frequencies using a hash map or fixed array and maintain a counter of characters whose frequency equals k. When the window size matches distinct * k and all tracked characters have frequency k, the substring is complete.

The adjacency constraint (|word[i] - word[i-1]| ā‰¤ 2) breaks the string into independent segments. If two neighboring characters differ by more than 2, no valid substring can cross that boundary. Split the string into such segments and run the sliding window logic inside each segment separately. This significantly reduces unnecessary checks.

This technique combines sliding window mechanics with a small hash table (or frequency array) to maintain counts efficiently while iterating through the string. Each index participates in a limited number of window adjustments, giving near-linear performance.

Recommended for interviews: Interviewers expect the sliding window solution. The brute force approach demonstrates that you understand the definition of a complete substring, but the optimized window with frequency tracking shows strong algorithmic thinking and familiarity with substring counting patterns.

Approach 1: Sliding Window with Frequency Map

Using a sliding window technique can help efficiently find substrings that meet the conditions. By utilizing a frequency map, keep track of character occurrences within the current window, and ensure that each character meets the exact frequency required. This helps quickly validate if the window is a potential 'complete' substring.

To handle the adjacency requirement, ensure that the absolute difference between any two adjacent character's ASCII values meets the condition within the same window.

This Python function leverages a sliding window approach with an integer array 'frequency' to count character occurrences. The 'start' pointer is adjusted whenever the conditions are violated, either by excess character frequency or window size exceeding possible options, and counts valid windows.

Code

PythonC++

Python

C++

Complexity

The time complexity of this function is O(n), where n is the length of the string. The space complexity is O(1), since the frequency array size is constant at 26.

Try this approach in the editor ā†’

Approach 2: Brute Force Substring Validation

This approach involves generating all possible substrings of 'word' and checking each substring for the character frequency and adjacency conditions. Though less efficient than the sliding window method, this is easier to implement and understand.

This Java solution uses a brute-force methodology to inspect each substring for potential completeness. The 'isValid' helper function ensures that each substring meets the frequency and adjacency rules.

Code

JavaC#

Java

C#

Complexity

The time complexity is O(n^3) due to the need for checking each possible substring. The space complexity is O(1) apart from the input as a constant array is used.

Try this approach in the editor ā†’

Approach 3: Enumerate Character Types + Sliding Window

According to condition 2 in the problem description, we can find that in a complete string, the difference between two adjacent characters does not exceed 2. Therefore, we traverse the string word, and we can use two pointers to split word into several substrings. The number of character types in these substrings does not exceed 26, and the difference between adjacent characters does not exceed 2. Next, we only need to count the number of substrings in each substring where each character appears k times.

We define a function f(s), which is used to count the number of substrings in the string s where each character appears k times. Since the number of character types in s does not exceed 26, we can enumerate each character type i, where 1 \le i \le 26, then the length of the substring with character type i is l = i times k.

We can use an array or hash table cnt to maintain the number of times each character appears in a sliding window of length l, and use another hash table freq to maintain the number of times each frequency appears. If freq[k] = i, that is, there are i characters that appear k times, then we have found a substring that meets the conditions. We can use two pointers to maintain this sliding window. Each time we move the right pointer, we increase the number of times the character pointed to by the right pointer appears and update the freq array; each time we move the left pointer, we decrease the number of times the character pointed to by the left pointer appears and update the freq array. After each pointer movement, we judge whether freq[k] is equal to i. If it is equal, it means that we have found a substring that meets the conditions.

The time complexity is O(n times |\Sigma|), and the space complexity is O(|\Sigma|), where n is the length of the string word; and \Sigma is the size of the character set. In this problem, the character set is lowercase English letters, so |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Sliding Window with Frequency Map

The time complexity of this function is O(n), where n is the length of the string. The space complexity is O(1), since the frequency array size is constant at 26.

Brute Force Substring Validation

The time complexity is O(n^3) due to the need for checking each possible substring. The space complexity is O(1) apart from the input as a constant array is used.

Enumerate Character Types + Sliding Windowā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring ValidationO(nĀ² * 26)O(26)Useful for understanding the definition of a complete substring or validating small inputs
Sliding Window with Frequency MapO(26 * n)O(26)General case and interview solution; efficiently counts valid substrings using fixed window sizes

Video Solution

Count Complete Substrings | Sliding Window | Weekly Contest 374 | Leetcode-2953 ā€¢ codestorywithMIK ā€¢ 10,283 views views

Watch 3 more video solutions ā†’

Frequently Asked Questions

Is Count Complete Substrings easy or hard?
Count Complete Substrings is categorized as a Hard problem because it combines multiple constraints: exact character frequency, adjacency rules, and efficient substring enumeration. Recognizing the fixed-length window pattern and segmenting the string is the main challenge.
How to solve Count Complete Substrings in O(n)?
Strict O(n) is not typical, but the practical optimal solution is O(26 * n), which behaves close to linear. Split the string into segments where adjacent characters differ by at most 2, then for each segment run sliding windows of size distinct Ɨ k while tracking frequencies.
Count Complete Substrings Python or Java solution?
Most implementations use a sliding window with a frequency array. Python and C++ versions typically use a list of size 26, while Java implementations often use an int[26] array for fast character counting.
What is the best approach for Count Complete Substrings?
The most efficient solution uses a sliding window with a frequency map. Iterate over possible numbers of distinct characters and maintain a window of length distinct Ɨ k while tracking character frequencies. Combined with splitting the string where adjacent character differences exceed 2, this runs in O(26 * n) time.
What data structure is used in Count Complete Substrings?
A frequency map or fixed-size array (size 26 for lowercase letters) tracks character counts inside the sliding window. Two pointers manage the window boundaries, making this a classic sliding window plus hash table pattern.
What is the time complexity of Count Complete Substrings?
The optimized sliding window solution runs in O(26 * n) time and O(26) space. The factor of 26 comes from iterating over possible distinct character counts. A brute force substring enumeration approach takes roughly O(nĀ²) time.
Is Count Complete Substrings asked at Google, Amazon, or Meta?
Problems combining sliding window, substring counting, and frequency constraints are common in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the pattern of fixed-length windows with frequency tracking appears frequently.

Ready to solve this problem?

Practice Count Complete Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Substrings Without Repeating Character

Next

Number of Substrings Containing All Three Characters