#2953

Hard

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count Complete Substrings

Count Complete Substrings involves finding substrings where each character appears exactly k times with constraints on adjacent characters.

hash table string sliding window

Problem Statement

You are given a string word and an integer k. A substring s of word is considered complete if each character in the substring appears exactly k times, and the difference between the indices of any two adjacent characters in the substring is at most 2.

Return the number of complete substrings of word. The solution requires efficiently counting valid substrings, and you can use techniques like sliding windows and hash tables to manage character counts and check constraints within the window.

Examples

Example 1

Input: word = "igigee", k = 2

Output: 3

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

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

Solution Approach

Sliding Window with Character Frequency Management

Use a sliding window to track substrings, expanding the window until the condition of having exactly k occurrences for each character is met. As the window expands, update the character frequency efficiently, and contract the window when constraints are violated.

Hash Table for Efficient Counting

Leverage a hash table to store the frequency of characters within the sliding window. This allows quick checks to ensure each character appears exactly k times, and updates can be made efficiently when characters are added or removed from the window.

Window Validation for Adjacent Character Difference

Alongside managing the frequency of characters, ensure that the difference in indices between adjacent characters within the window does not exceed 2. This will require careful tracking of character positions and checking the distance between them as the window slides.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the final approach, particularly the window size and the efficiency of updating the hash table. In the optimal case, the complexity can be reduced to O(n), where n is the length of the word, by efficiently expanding and contracting the window while keeping track of character frequencies and adjacent character positions.

What Interviewers Usually Probe

Look for understanding of sliding window techniques and how they can be adapted to maintain state in a problem like this.
Check the candidate's ability to use hash tables efficiently, especially in terms of managing dynamic frequencies within a sliding window.
Evaluate the candidate’s approach to validating substring constraints, specifically handling the adjacency condition and frequency checks simultaneously.

Common Pitfalls or Variants

Common pitfalls

Failing to efficiently manage the sliding window or hash table, leading to excessive time complexity.
Incorrectly handling edge cases where there are no valid complete substrings or when k is very large relative to the word length.
Overcomplicating the problem by attempting unnecessary optimizations or brute force methods instead of leveraging efficient window management.

Follow-up variants

Increasing k or the length of the word, requiring more sophisticated state management in the sliding window.
Handling multiple overlapping valid substrings and ensuring they are counted correctly without duplication.
Modifying the condition for adjacency or frequency, e.g., allowing for a larger difference between characters or a range of allowed frequencies.

FAQ

What is the best approach for solving Count Complete Substrings?

The best approach uses a sliding window with character frequency management through a hash table, ensuring the constraints are maintained efficiently.

How does sliding window apply to this problem?

The sliding window is used to track substrings dynamically, adjusting the window size while maintaining the frequency of characters and ensuring adjacent character constraints.

What are common mistakes when solving Count Complete Substrings?

Common mistakes include inefficient window management, incorrect handling of edge cases, and failing to properly track character frequencies within the sliding window.

Can this problem be solved in O(n) time?

Yes, if the sliding window is managed efficiently and the hash table is used to track frequencies and positions, the problem can be solved in O(n) time.

How does GhostInterview help with Count Complete Substrings?

GhostInterview helps by providing step-by-step guidance on applying sliding window and hash table techniques, focusing on efficiency and handling edge cases.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def countCompleteSubstrings(self, word: str, k: int) -> int:
        def f(s: str) -> int:
            m = len(s)
            ans = 0
            for i in range(1, 27):
                l = i * k
                if l > m:
                    break
                cnt = Counter(s[:l])
                freq = Counter(cnt.values())
                ans += freq[k] == i
                for j in range(l, m):
                    freq[cnt[s[j]]] -= 1
                    cnt[s[j]] += 1
                    freq[cnt[s[j]]] += 1

                    freq[cnt[s[j - l]]] -= 1
                    cnt[s[j - l]] -= 1
                    freq[cnt[s[j - l]]] += 1

                    ans += freq[k] == i
            return ans

        n = len(word)
        ans = i = 0
        while i < n:
            j = i + 1
            while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2:
                j += 1
            ans += f(word[i:j])
            i = j
        return ans

Continue Practicing

#2981 find longest special substring that occurs thrice i #2982 find longest special substring that occurs thrice ii #3090 maximum length substring with two occurrences