We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Special Substring of Length K

Number: 3709

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a string s and an integer k, determine if there exists a substring of length exactly k which consists of only one distinct character, and if present, its immediate neighbors (if any) are different from this character.

Key Insights

  • The substring must have k identical characters.
  • The character immediately before the substring (if it exists) must differ from the substring’s character.
  • The character immediately after the substring (if it exists) must also differ.
  • Because the string length is at most 100, a simple linear scan checking every possible substring of length k is efficient.

Space and Time Complexity

Time Complexity: O(n * k), where n is the length of the string (acceptable given n ≤ 100). Space Complexity: O(1), constant extra space is used.

Solution

We iterate over all possible starting indices i such that the substring s[i...i+k-1] is a candidate. For each candidate:

  1. Check if all characters in s[i...i+k-1] are the same.
  2. Verify that if i > 0, then s[i-1] is not the same as s[i].
  3. Verify that if i+k < n, then s[i+k] is not the same as s[i]. If a candidate meets all conditions, return true. If no candidate meets the conditions after scanning the string, return false. This approach uses a simple loop with character comparisons to achieve the result.

Code Solutions

def find_special_substring(s: str, k: int) -> bool:
    n = len(s)
    # Iterate over every possible substring of length k.
    for i in range(n - k + 1):
        # Check if the substring consists of one distinct character.
        if s[i] * k == s[i:i + k]:
            # Verify the character before the substring, if it exists.
            if i > 0 and s[i - 1] == s[i]:
                continue
            # Verify the character after the substring, if it exists.
            if i + k < n and s[i + k] == s[i]:
                continue
            return True  # Found a valid substring.
    return False  # No valid substring found.

# Example usage:
print(find_special_substring("aaabaaa", 3))  # Expected output: True
print(find_special_substring("abc", 2))      # Expected output: False
← Back to All Questions