# Find Special Substring of Length K
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-special-substring-of-length-k)
Canonical: https://scaleengineer.com/dsa/problems/find-special-substring-of-length-k
**Data structures:** String
---
## 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`.

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

# Approaches
## Brute-Force Substring Check
This approach directly translates the problem statement into code. It iterates through every possible substring of length `k` and, for each one, verifies if it meets all three specified conditions.
**Time:** O(n * k), where `n` is the length of `s`. The outer loop runs `n-k+1` times (which is O(n)), and the inner check for character homogeneity takes `O(k)` time in the worst case. · **Space:** O(1), as we only use a few variables to store indices and characters, requiring constant extra space.
**Pros:** Simple to understand and implement directly from the problem description.; Correctly solves the problem for all valid inputs.
**Cons:** Inefficient due to the nested loop structure, with a time complexity of O(n*k).; Performs redundant checks, as overlapping substrings are re-evaluated from scratch.
### Explanation
The algorithm iterates from the first possible starting position of a substring of length `k` (index 0) up to the last possible one (index `n-k`, where `n` is the string length).

For each starting index `i`, we consider the substring `s[i...i+k-1]`.

We then perform three checks:
1.  **Homogeneous Characters:** A nested loop checks if all characters from `s[i+1]` to `s[i+k-1]` are identical to `s[i]`. If not, we move to the next starting index `i+1`.
2.  **Preceding Character:** If the substring doesn't start at the beginning of the string (`i > 0`), we check if the character `s[i-1]` is different from the substring's character `s[i]`.
3.  **Succeeding Character:** If the substring doesn't end at the very end of the string (`i+k < n`), we check if the character `s[i+k]` is different from the substring's character `s[i]`.

If a substring passes all three checks, we have found a special substring, and the function immediately returns `true`.

If the outer loop completes without finding any such substring, it means none exist, and the function returns `false`.

```java
class Solution {
    public boolean findSpecialSubstring(String s, int k) {
        int n = s.length();
        if (k > n) {
            return false;
        }

        // Iterate through all possible start indices of a substring of length k
        for (int i = 0; i <= n - k; i++) {
            char firstChar = s.charAt(i);

            // Condition 1: All characters in the substring are the same
            boolean allSame = true;
            for (int j = 1; j < k; j++) {
                if (s.charAt(i + j) != firstChar) {
                    allSame = false;
                    break;
                }
            }
            if (!allSame) {
                continue;
            }

            // Condition 2: Character before is different
            boolean beforeIsDifferent = (i == 0) || (s.charAt(i - 1) != firstChar);

            // Condition 3: Character after is different
            boolean afterIsDifferent = (i + k == n) || (s.charAt(i + k) != firstChar);

            if (beforeIsDifferent && afterIsDifferent) {
                return true; // Found a special substring
            }
        }

        return false; // No special substring found
    }
}
```
### Algorithm
- Iterate with an index `i` from `0` to `s.length() - k`.
- Inside the loop, consider the substring `s[i...i+k-1]` as a candidate.
- **Check Condition 1:** Verify that all characters in `s[i...i+k-1]` are the same. If not, `continue` to the next `i`.
- **Check Condition 2:** Check if the character before the substring (if it exists, i.e., `i > 0`) is different from the substring's character. 
- **Check Condition 3:** Check if the character after the substring (if it exists, i.e., `i + k < s.length()`) is different from the substring's character.
- If all three conditions are met, return `true`.
- If the loop finishes without finding a valid substring, return `false`.

## Single Pass by Grouping Consecutive Characters
A more efficient approach is to reframe the problem. A "special substring" of length `k` is essentially a maximal block of identical characters whose length is exactly `k`. A maximal block is one that is bordered by different characters or the ends of the string. This approach iterates through the string once to find the lengths of these consecutive character groups.
**Time:** O(n), where `n` is the length of `s`. We iterate through the string only once, making it a linear time solution. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop index.
**Pros:** Highly efficient with optimal linear time complexity.; Avoids redundant checks by processing each character only once.
**Cons:** The logic is slightly less direct than the brute-force approach.; Requires careful handling of the edge case for the last group of characters after the loop finishes.
### Explanation
The algorithm scans the string from left to right, keeping a count of the current number of consecutive identical characters.

We initialize a `count` to 1 and start iterating from the second character of the string (`i=1`).

In each step, we compare the current character `s[i]` with the previous one `s[i-1]`.
- If they are the same, we increment our `count`.
- If they are different, it signifies the end of a consecutive block. We then check if the `count` of the block that just ended is equal to `k`. If it is, we've found our special substring and can return `true`. After the check, we reset the `count` to 1 for the new block starting with `s[i]`.

A special case is the very last block of characters in the string. Its end is not marked by a different character but by the end of the string itself. Therefore, after the loop finishes, we must perform one final check on the current `count` to see if the last block has a length of `k`.

If the loop completes and the final check fails, no special substring was found, and we return `false`.

```java
class Solution {
    public boolean findSpecialSubstring(String s, int k) {
        int n = s.length();
        if (n < k) {
            return false;
        }
        
        int consecutiveCount = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                consecutiveCount++;
            } else {
                // A new character group starts, check the length of the previous one.
                if (consecutiveCount == k) {
                    return true;
                }
                // Reset count for the new group.
                consecutiveCount = 1;
            }
        }

        // After the loop, check the length of the last group of characters.
        return consecutiveCount == k;
    }
}
```
### Algorithm
- If `s.length() < k`, return `false` immediately.
- Initialize `consecutiveCount = 1` (for the first character's group).
- Iterate with an index `i` from `1` to `s.length() - 1`.
- If `s.charAt(i) == s.charAt(i - 1)`, increment `consecutiveCount`.
- Else (if `s.charAt(i) != s.charAt(i - 1)`), a group has ended:
    - Check if `consecutiveCount == k`. If true, return `true`.
    - Reset `consecutiveCount = 1` for the new group.
- After the loop, the last group hasn't been checked. Perform a final check: if `consecutiveCount == k`, return `true`.
- If no such group was found, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean hasSpecialSubstring(String s, int k) {
    int n = s.length();
    for (int l = 0, cnt = 0; l < n;) {
      int r = l + 1;
      while (r < n && s.charAt(r) == s.charAt(l)) {
        ++r;
      }
      if (r - l == k) {
        return true;
      }
      l = r;
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool hasSpecialSubstring(string s, int k) {
    int n = s.length();
    for (int l = 0, cnt = 0; l < n;) {
      int r = l + 1;
      while (r < n && s[r] == s[l]) {
        ++r;
      }
      if (r - l == k) {
        return true;
      }
      l = r;
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def hasSpecialSubstring(self, s: str, k: int) -> bool: l, n = 0, len(s) while l < n: r = l while r < n and s[r] == s[l]: r += 1 if r - l == k: return True l = r return False

```