Find Special Substring of Length K

EASY

Description

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:

The substring consists of only one distinct character (e.g., "aaa" or "bbb").
If there is a character immediately before the substring, it must be different from the character in the substring.
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

Checkout 2 different approaches to solve Find Special Substring of Length K. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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:

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

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
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store indices and characters, requiring constant extra space.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Special Substring of Length K. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Find Special Substring of Length K

Data Structures:

String