Find Special Substring of Length K

Difficulty: Easy | Acceptance: 35.20% | Paid: No Topics: String

You are given a string s and an integer k. A substring is called special if all characters in the substring are the same. Return the number of special substrings of length k in s.

• Examples
• Constraints
• Brute Force
• Linear Scan

Examples

Example 1

Input:

s = "aaabaaa", k = 3

Output:

true

Explanation: The substring s[4..6] == “aaa” satisfies the conditions.

It has a length of 3.

All characters are the same.

The character before “aaa” is ‘b’, which is different from ‘a’.

There is no character after “aaa”.

Example 2

Input:

s = "abc", k = 2

Output:

false

Explanation: There is no substring of length 2 that consists of one distinct character and satisfies the conditions.

Constraints

1 <= s.length <= 10⁵
1 <= k <= s.length
s consists of lowercase English letters.

Brute Force

Intuition We can iterate through every possible starting index for a substring of length k and check if all characters in that window are identical.

Steps

• Iterate i from 0 to len(s) - k.
• For each i, extract the substring s[i : i+k].
• Check if the set of characters in this substring has a size of 1.
• If yes, increment the count.

class Solution:
    def countSpecialSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        count = 0
        for i in range(n - k + 1):
            # Check if all characters in the window are the same
            if len(set(s[i:i+k])) == 1:
                count += 1
        return count

Complexity

• Time: O(n * k), where n is the length of the string. In the worst case, we check k characters for each of the n starting positions.
• Space: O(1) or O(k) depending on how the substring check is implemented (e.g., creating a set takes O(k) space).
• Notes: This approach is simple but may be too slow for large inputs (n up to 10⁵) if k is also large.

Linear Scan

Intuition Instead of checking every window, we can identify contiguous blocks of identical characters. For a block of length L, the number of substrings of length k that fit entirely within this block is L - k + 1 (if L >= k).

Steps

• Initialize a pointer i to 0.
• While i is less than the length of s:
  • Expand a window starting at i as long as the characters are the same. Let j be the end of this window.
  • Calculate the length of the block: length = j - i.
  • If length >= k, add length - k + 1 to the result.
  • Move i to j to start the next block.

class Solution:
    def countSpecialSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        res = 0
        i = 0
        while i < n:
            j = i
            # Expand the window while characters are the same
            while j < n and s[j] == s[i]:
                j += 1
            length = j - i
            # Calculate number of valid substrings in this block
            if length >= k:
                res += length - k + 1
            i = j
        return res

Complexity

• Time: O(n), where n is the length of the string. We traverse the string exactly once.
• Space: O(1), we only use a few variables for pointers and counters.
• Notes: This is the optimal solution for this problem.