Scale Engineer

Find Special Substring of Length K

Easy
#3072Time: 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.
Data structures
String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

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

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem