Find Special Substring of Length K

Problem

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.

Examples

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.

Solution

Method 1 – Sliding Window and Character Check

Intuition

We can use a sliding window of length k to check each substring. For each window, we check if all characters are the same, and if the characters before and after the window (if they exist) are different from the window character.

Approach

1. Iterate over all possible substrings of length k in s.
2. For each substring:
   • Check if all characters are the same.
   • If there is a character before the substring, check it is different from the window character.
   • If there is a character after the substring, check it is different from the window character.
3. If any substring satisfies all conditions, return true.
4. If no such substring exists, return false.

Code

C++

class Solution {
public:
    bool hasSpecialSubstring(string s, int k) {
        int n = s.size();
        for (int i = 0; i + k <= n; ++i) {
            char c = s[i];
            bool ok = true;
            for (int j = 1; j < k; ++j) if (s[i+j] != c) { ok = false; break; }
            if (!ok) continue;
            if (i > 0 && s[i-1] == c) continue;
            if (i + k < n && s[i+k] == c) continue;
            return true;
        }
        return false;
    }
};

Go

func hasSpecialSubstring(s string, k int) bool {
    n := len(s)
    for i := 0; i+k <= n; i++ {
        c := s[i]
        ok := true
        for j := 1; j < k; j++ {
            if s[i+j] != c {
                ok = false
                break
            }
        }
        if !ok { continue }
        if i > 0 && s[i-1] == c { continue }
        if i+k < n && s[i+k] == c { continue }
        return true
    }
    return false
}

Java

class Solution {
    public boolean hasSpecialSubstring(String s, int k) {
        int n = s.length();
        for (int i = 0; i + k <= n; i++) {
            char c = s.charAt(i);
            boolean ok = true;
            for (int j = 1; j < k; j++) if (s.charAt(i+j) != c) { ok = false; break; }
            if (!ok) continue;
            if (i > 0 && s.charAt(i-1) == c) continue;
            if (i + k < n && s.charAt(i+k) == c) continue;
            return true;
        }
        return false;
    }
}

Kotlin

class Solution {
    fun hasSpecialSubstring(s: String, k: Int): Boolean {
        val n = s.length
        for (i in 0..n-k) {
            val c = s[i]
            if ((1 until k).any { s[i+it] != c }) continue
            if (i > 0 && s[i-1] == c) continue
            if (i + k < n && s[i+k] == c) continue
            return true
        }
        return false
    }
}

Python

class Solution:
    def hasSpecialSubstring(self, s: str, k: int) -> bool:
        n = len(s)
        for i in range(n - k + 1):
            c = s[i]
            if any(s[i+j] != c for j in range(k)):
                continue
            if i > 0 and s[i-1] == c:
                continue
            if i + k < n and s[i+k] == c:
                continue
            return True
        return False

Rust

impl Solution {
    pub fn has_special_substring(s: String, k: i32) -> bool {
        let n = s.len();
        let s = s.as_bytes();
        let k = k as usize;
        for i in 0..=n-k {
            let c = s[i];
            if (1..k).any(|j| s[i+j] != c) { continue; }
            if i > 0 && s[i-1] == c { continue; }
            if i + k < n && s[i+k] == c { continue; }
            return true;
        }
        false
    }
}

TypeScript

class Solution {
    hasSpecialSubstring(s: string, k: number): boolean {
        const n = s.length;
        for (let i = 0; i + k <= n; i++) {
            const c = s[i];
            if ([...Array(k).keys()].some(j => s[i+j] !== c)) continue;
            if (i > 0 && s[i-1] === c) continue;
            if (i + k < n && s[i+k] === c) continue;
            return true;
        }
        return false;
    }
}

Complexity

• ⏰ Time complexity: O(nk), where n is the length of s and k is the substring length, since we check each substring of length k.
• 🧺 Space complexity: O(1), as we use only a few variables.