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

Intuition

The problem requires finding consecutive identical characters in the string that form a segment of exact length k, ensuring that the characters before and after this segment differ from it, if they exist.

The solution approach uses the two-pointer technique:

1. Initialize two pointers, l and r, both starting at the beginning of the string s.
2. Expand the right pointer r as long as the character at this pointer matches the character at l. This identifies a segment of consecutive identical characters.
3. Once a different character is found or the end of the string is reached, check if the length of this segment (r - l) is exactly k.
4. If such a segment is found, return true. Otherwise, reset l to r and continue searching through the string.
5. If no suitable segment is found by the end of the string, return false.

This approach effectively traverses the string, examining each segment of consecutive identical characters efficiently.

Solution Approach

To solve this problem, the Two Pointers technique is adopted, aiming to efficiently identify segments of consecutive identical characters in the string s of exact length k. Here is the detailed approach:

1. Initialize a pointer l at the start of the string and calculate the length n of the string s.

2. Use a loop to increment the pointer l until reaching the end of the string:

   • Within this loop, initialize another pointer r starting from l. Move r to the right as long as s[r] is equal to s[l]. This process identifies a block of consecutive identical characters.

   • Once a character different from s[l] is encountered or the end of the string is reached, check the length of this block: if r - l equals k, it means a valid substring is found, and the function should return True.

3. If the loop completes without finding any valid substring, return False.

The approach efficiently checks each character only once and correctly identifies segments of exact length k, making it optimal for the given problem constraints. The algorithm can be represented as follows:

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

This solution leverages the simple yet powerful two-pointer technique, which ensures traversal of the string is efficient, achieving the goal with minimal iterations.

Example Walkthrough

Let's walk through the solution with an example. Consider the string s = "aabbba" and k = 3.

1. Initialization:

   • Start with pointers l and r at the beginning of the string (l = 0, r = 0).
   • The length of the string n is 6.

2. First iteration:

   • l = 0: Character at s[l] is 'a'.
   • Move r to the right as long as s[r] is equal to s[l].
   • The substring from s[0] to s[1] is "aa". Since r becomes 2 and (r - l equals 2), it's not equal to k. So, reset l to r (now both l and r are 2).

3. Second iteration:

   • l = 2: Character at s[l] is 'b'.
   • Move r to the right as long as s[r] equals s[l].
   • The substring from s[2] to s[4] is "bbb". Here, r becomes 5 and (r - l equals 3). This matches k, and the character immediately before the substring s[1] is 'a', which is different from 'b'. Hence, the conditions are satisfied.
   • Return True.

With this example, the solution evaluates each block of consecutive characters and checks if the conditions are satisfied efficiently using the two-pointer approach.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the algorithm makes a single pass through the string, checking consecutive characters and counting their occurrences without revisiting any part of the string.

The space complexity of the code is O(1), as it utilizes a constant amount of extra space for variables l, r, and n, irrespective of the size of the input string.

Learn more about how to find time and space complexity quickly.