You are given a string s and an integer k.
Determine if there exists a substring of length exactly k in s that satisfies the following conditions:
"aaa" or "bbb").Return true if such a substring exists. Otherwise, return false.
Example 1:
Input: s = "aaabaaa", k = 3
Output: true
Explanation:
The substring s[4..6] == "aaa" satisfies the conditions.
"aaa" is 'b', which is different from 'a'."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 <= k <= s.length <= 100s consists of lowercase English letters only.Problem Overview: You get a string s and an integer k. The goal is to check whether the string contains a special substring of length k. A substring is special if all characters inside it are identical and the substring is not part of a longer block of the same character (the characters just outside the substring must be different or out of bounds).
Approach 1: Brute Force Window Check (O(n * k) time, O(1) space)
Slide a window of size k across the string. For each starting index i, first verify that all characters in s[i..i+k-1] are the same by iterating through the window. If they match, check the boundaries: s[i-1] (if it exists) must be different from s[i], and s[i+k] (if it exists) must also be different. This ensures the substring is exactly length k and not part of a longer sequence. The approach is simple but can re-check the same characters many times, giving O(n * k) time complexity.
Approach 2: Two Pointers / Run-Length Scan (O(n) time, O(1) space)
Instead of checking every window, scan the string and group consecutive identical characters using a two pointers technique. Maintain a start pointer for the current block and expand the end pointer while characters match. This effectively computes the length of each run of identical characters. If any run has length exactly k, that block already satisfies the boundary condition because the characters before and after the run are different (or the run touches the string edge). Once a block is processed, move the start pointer to the next new character. Each character is visited once, so the total time is O(n) with constant extra space.
This pattern is common in string problems where you analyze contiguous segments instead of fixed windows. It avoids redundant comparisons and turns the problem into a linear scan.
Recommended for interviews: The two pointers run-length approach. The brute force method shows you understand the definition of a valid substring, but interviewers usually expect the O(n) scan. It demonstrates you can compress repeated characters into segments and reason about boundaries efficiently.
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 true; otherwise, return false.
We can use two pointers l and r to traverse the string s. When s[l] = s[r], move r to the right until s[r] neq s[l]. At this point, check if r - l equals k. If it does, return true; otherwise, move l to r and continue traversing.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Check | O(n * k) | O(1) | Good for understanding the definition of a special substring and verifying edge conditions. |
| Two Pointers (Run-Length Scan) | O(n) | O(1) | Best choice for production and interviews. Efficiently processes consecutive character groups in a single pass. |
Find special substring of length k | Leetcode weekly contest 437 solutions • CodeCrusher • 863 views views
Watch 9 more video solutions →Practice Find Special Substring of Length K with our built-in code editor and test cases.
Practice on FleetCode