Skip to main content
Talentd

Find Special Substring of Length K - Solution & Explanation

EasyString7 min readAsked at: Amazon
Practice this problem

Problem Statement

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:

  1. The substring consists of only one distinct character (e.g., "aaa" or "bbb").
  2. If there is a character immediately before the substring, it must be different from the character in the substring.
  3. If there is a character immediately after the substring, it must also be different from the character in the substring.

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.

  • 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 <= k <= s.length <= 100
  • s consists of lowercase English letters only.

Approach Overview

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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window CheckO(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.

Video Solution

Find special substring of length k | Leetcode weekly contest 437 solutions • CodeCrusher • 863 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Special Substring of Length K easy or hard?
Find Special Substring of Length K is categorized as an Easy problem. The main skill tested is recognizing that contiguous identical characters can be grouped and evaluated using a linear scan instead of repeatedly checking every substring window.
Find Special Substring of Length K Python/Java solution
Python, Java, C++, Go, and TypeScript implementations typically follow the same pattern: iterate through the string, count the length of each contiguous block of identical characters, and check whether any block length equals k. The logic remains O(n) time and O(1) space across languages.
How to solve Find Special Substring of Length K in O(n)?
Traverse the string while grouping consecutive identical characters. Maintain a start index for the current run and extend it while the characters match. When the run ends, compute its length; if the length equals k, the substring satisfies the requirement because the neighbors are different or out of bounds. Continue scanning until the end of the string.
What is the best approach for Find Special Substring of Length K?
The optimal solution uses a two pointers scan that groups consecutive identical characters. By computing the length of each run of the same character, you can immediately check if any run has length exactly k. This approach runs in O(n) time and O(1) space because each character is processed once.
Is Find Special Substring of Length K asked at Google/Amazon/Meta?
This style of problem appears frequently in interviews that test string scanning and two pointers techniques. While the exact problem number may vary, similar tasks involving contiguous character runs or substring validation show up in interviews at companies like Amazon and Google.
What data structure is used in Find Special Substring of Length K?
The problem mainly relies on string traversal with the two pointers technique. No additional data structures are required because the solution only tracks indices and counts while scanning consecutive characters.
What is the time complexity of Find Special Substring of Length K?
The optimal two pointers solution runs in O(n) time, where n is the length of the string. Each character is visited once while forming contiguous runs. Space complexity is O(1) since only a few indices and counters are stored.

Ready to solve this problem?

Practice Find Special Substring of Length K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring