Watch 10 video solutions for Find Special Substring of Length K, a easy level problem involving String. This walkthrough by CodeCrusher has 863 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |