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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Special Substring of Length K

Difficulty: Easy

Problem Description

You are given a string s and an integer k. Determine if there exists a substring of length exactly k in s that consists of only one distinct character and is surrounded by different characters on both sides. Return true if such a substring exists; otherwise, return false.

Key Insights

  • The substring must have a length of exactly k.
  • All characters in the substring must be the same.
  • The character immediately before the substring must differ from the character in the substring.
  • The character immediately after the substring must also differ from the character in the substring.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(1), as we only use a constant amount of extra space.

Solution

To solve this problem, we can iterate through the string while checking for potential substrings of length k. For each character in the string, we check if it forms a valid substring of length k with the following conditions:

  1. All characters in that substring must be the same.
  2. The character before the substring (if it exists) must be different from the character in the substring.
  3. The character after the substring (if it exists) must also be different from the character in the substring.

If we find such a substring, we return true. If we finish checking the string without finding one, we return false.

Code Solutions

def find_special_substring(s: str, k: int) -> bool:
    n = len(s)
    
    for i in range(n - k + 1):
        substring = s[i:i + k]
        if len(set(substring)) == 1:  # Check if all characters are the same
            # Check characters before and after the substring
            before = s[i - 1] if i > 0 else None
            after = s[i + k] if i + k < n else None
            
            if (before is None or before != substring[0]) and (after is None or after != substring[0]):
                return True
    
    return False
← Back to All Questions