#3456

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Find Special Substring of Length K

Check efficiently if a string contains a consecutive sequence of length k where all characters match exactly one distinct letter.

string

Problem Statement

Given a string s and an integer k, determine whether s contains a contiguous substring of length k where all characters are identical. The substring must consist of exactly k consecutive identical characters.

Return true if at least one such substring exists in s. Otherwise, return false. Constraints include 1 <= k <= s.length and lowercase English letters only in s.

Examples

Example 1

Input: s = "aaabaaa", k = 3

Output: true

The substring s[4..6] == "aaa" satisfies the conditions.

Example 2

Input: s = "abc", k = 2

Output: false

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

Constraints

1 <= k <= s.length <= 100
s consists of lowercase English letters only.

Solution Approach

Sliding Window with Consecutive Count

Use a sliding window of size k and maintain a count of consecutive identical characters. Move the window through s and reset the count whenever the character changes. Return true immediately once the count reaches k.

Early Exit Optimization

Iterate through s while checking for consecutive repeats. If the remaining length is less than k, exit early since no valid substring can exist beyond this point, reducing unnecessary computation.

Single Pass Scan

Traverse the string once, keeping track of the current character and its consecutive frequency. This ensures O(n) time complexity and O(1) space, directly targeting the string-driven solution strategy of this problem.

Complexity Analysis

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

Time complexity is O(n) because each character is visited once. Space complexity is O(1) since only counters and current character tracking are used.

What Interviewers Usually Probe

Emphasizes whether you recognize the string-driven pattern for consecutive identical characters.
Checks if you can optimize by early exit when substring length cannot be satisfied.
Wants clear O(n) traversal without extra data structures.

Common Pitfalls or Variants

Common pitfalls

Counting non-consecutive identical characters incorrectly across gaps.
Not handling edge cases where k equals string length or 1.
Forgetting to reset the consecutive counter when characters change.

Follow-up variants

Check for substrings with exactly two distinct characters repeating alternately.
Find the longest substring of consecutive identical characters instead of fixed length k.
Return all starting indices of valid substrings rather than a boolean result.

FAQ

What is the simplest way to check for a substring of length k with identical characters?

Use a single pass with a counter for consecutive characters and reset it when the character changes. Return true when the counter reaches k.

Can k be larger than the string length?

No, k must satisfy 1 <= k <= s.length according to the constraints.

Does the string-driven solution require extra space?

No, you only need a few variables to track the current character and consecutive count, so space is O(1).

How does the early exit optimization help?

If the remaining characters in s are fewer than k, you can exit early since no substring can satisfy the condition, saving time.

Is this problem pattern only about consecutive identical characters?

Yes, the main focus is detecting sequences of exactly k identical characters, which defines the string-driven solution strategy.

terminal

Solution

Solution 1: Two Pointers

The problem essentially asks us to find each segment of consecutive identical characters and then determine if there exists a substring of length $k$. If such a substring exists, return $\textit{true}$; otherwise, return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def hasSpecialSubstring(self, s: str, k: int) -> bool:
        l, n = 0, len(s)
        while l < n:
            r = l
            while r < n and s[r] == s[l]:
                r += 1
            if r - l == k:
                return True
            l = r
        return False

Continue Practicing

#3455 shortest matching substring #3458 select k disjoint special substrings #3461 check if digits are equal in string after operations i