Find Special Substring of Length K

Easy
1776.

Find Special Substring of Length K

Find Special Substring of Length K is an easy coding problem on strings, asked in Amazon interviews.

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 <= 100
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var hasSpecialSubstring = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Find Special Substring of Length K

  1. Hint 1

    The conditions say the substring cannot be extended on either side with the same letter.

  2. Hint 2

    So it is exactly a maximal run of one letter — and its length must be k.

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

  1. Walk s, measuring each maximal run of one letter.
  2. If a run has length exactly k, return true.
  3. Return false after 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-k block: "bbbb" with k = 2 is 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 False

Java

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