Find Special Substring of Length K — Problem & Solution
Find Special Substring of Length K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Special Substring of Length K is an easy coding problem on strings, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and an integer k.
Decide whether s has a substring of length exactly k such that:
- all of its characters are the same letter
c; - the character just before it (if there is one) is not
c; - the character just after it (if there is one) is not
c.
Return true if such a substring exists, otherwise false.
Example 1
Input: s = "aaabaaa", k = 3
Output: true
Explanation: "aaa" at the start is followed by 'b' and has nothing before it.
Example 2
Input: s = "abc", k = 2
Output: false
Explanation: No two neighbouring letters are equal.
Example 3
Input: s = "bbbb", k = 2
Output: false
Explanation: Every "bb" touches another 'b' on at least one side.
Constraints
1 <= k <= s.length <= 100s consists only of lowercase English letters
Hints for Find Special Substring of Length K
Hint 1
The conditions say the substring cannot be extended on either side with the same letter.
Hint 2
So it is exactly a maximal run of one letter — and its length must be
k.Hint 3
Scan the runs of equal letters and check whether any run has length exactly
k.
How to solve Find Special Substring of Length K
A block of k equal letters whose neighbours differ from them is precisely a maximal run of length k. So the answer is whether some maximal run has length exactly k.
Approach
- Walk
s, measuring each maximal run of one letter. - If a run has length exactly
k, returntrue. - Return
falseafter the scan.
Why it works
A qualifying substring cannot be extended (its neighbours differ) and contains only one letter, so it is a whole maximal run. Conversely a maximal run of length k satisfies all three conditions.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A longer run does not contain a valid length-
kblock: "bbbb" withk = 2is false. - The last run ends at the end of the string — check it after the loop if your scan only checks on a letter change.
Reference solution
Python
def hasSpecialSubstring(s: str, k: int) -> bool:
n, i = len(s), 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
if j - i == k:
return True
i = j
return FalseJava
public static boolean hasSpecialSubstring(String s, int k) {
int n = s.length(), i = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) j++;
if (j - i == k) return true;
i = j;
}
return false;
}C++
bool hasSpecialSubstring(string s, int k) {
int n = s.size(), i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] == s[i]) j++;
if (j - i == k) return true;
i = j;
}
return false;
}JavaScript
var hasSpecialSubstring = function(s, k) {
var n = s.length, i = 0;
while (i < n) {
var j = i;
while (j < n && s[j] === s[i]) j++;
if (j - i === k) return true;
i = j;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings