Count Complete Substrings - Practice Coding Problems

Count Complete Substrings - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "aaabbbccc", k = 3

› Output: 3

💡 Note: Complete substrings: "aaabbb" (a:3, b:3), "bbbccc" (b:3, c:3), "aaabbbccc" (a:3, b:3, c:3). All satisfy adjacency rule since |a-b|=1≤2 and |b-c|=1≤2.

Example 2 — No Valid Substrings

$ Input: word = "aaabbbccc", k = 2

› Output: 0

💡 Note: No substring has each character appearing exactly 2 times. The string has 3 of each character, which doesn't match k=2.

Example 3 — Adjacency Violation

$ Input: word = "aaafff", k = 3

› Output: 0

💡 Note: Although "aaa" and "fff" individually have characters appearing 3 times, |a-f|=5>2 violates adjacency rule, so no complete substrings exist.

Constraints

1 ≤ word.length ≤ 1000
1 ≤ k ≤ word.length
word consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String "aaabbbccc" and k=3

Check Constraints

Find substrings where each character appears exactly k times and adjacency rule holds

Output

Count of valid complete substrings: 3

Key Takeaway

🎯 Key Insight: Split string by adjacency violations, then use sliding window to efficiently count substrings with exact character frequencies

Asked in

G Google 15 M Microsoft 12 a Amazon 10

The key insight is to split the string into segments where adjacency constraints are satisfied, then use sliding window technique to efficiently find substrings with exact character frequencies. The optimal approach uses sliding window with frequency tracking achieving O(n × 26) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Sliding Window	O(n × 26)	O(1)	Split by invalid adjacencies, then use sliding window on valid segments
Brute Force	O(n³)	O(1)	Check every possible substring for both conditions

Optimized Sliding Window — Algorithm Steps

Split string into valid adjacency segments
For each segment, try all possible unique character counts
Use sliding window to find substrings with exactly k occurrences of each character
Count all valid windows

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Segments

Divide string at points where adjacency rule breaks

Sliding Window

For each segment, use window to find valid substrings

Count Valid

Count windows with exact frequency requirements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int countCompleteInSegment(char* segment, int len, int k) {
    int count = 0;
    
    // Try all possible number of unique characters (1 to 26)
    for (int uniqueChars = 1; uniqueChars <= 26; uniqueChars++) {
        if (uniqueChars * k > len) break;
        
        // Sliding window for exactly uniqueChars distinct characters
        int freq[26] = {0};
        int distinctCount = 0;
        int left = 0;
        
        for (int right = 0; right < len; right++) {
            int idx = segment[right] - 'a';
            if (freq[idx] == 0) distinctCount++;
            freq[idx]++;
            
            // Shrink window if we have too many distinct characters
            while (distinctCount > uniqueChars) {
                int leftIdx = segment[left] - 'a';
                freq[leftIdx]--;
                if (freq[leftIdx] == 0) distinctCount--;
                left++;
            }
            
            // Check if current window is valid
            if (distinctCount == uniqueChars && (right - left + 1) == uniqueChars * k) {
                bool valid = true;
                for (int i = 0; i < 26; i++) {
                    if (freq[i] > 0 && freq[i] != k) {
                        valid = false;
                        break;
                    }
                }
                if (valid) count++;
            }
        }
    }
    
    return count;
}

int solution(char* word, int k) {
    int n = strlen(word);
    int totalCount = 0;
    int start = 0;
    
    for (int i = 0; i <= n; i++) {
        if (i == n || (i > 0 && abs(word[i] - word[i-1]) > 2)) {
            if (i > start) {
                totalCount += countCompleteInSegment(word + start, i - start, k);
            }
            start = i;
        }
    }
    
    return totalCount;
}

int main() {
    char word[1001];
    int k;
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(word, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 26)

For each position, we check at most 26 different character counts with sliding window

✓ Linear Growth

Space Complexity

O(1)

Only using constant space for frequency counting (at most 26 characters)

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler