Problem Description

You are given a string s and an integer k. Your task is to determine if there exists a substring in s that meets all of the following conditions:

1. The substring has exactly length k
2. The substring consists of only one repeated character (like "aaa" or "bbb")
3. If there's a character immediately before this substring, it must be different from the character in the substring
4. If there's a character immediately after this substring, it must be different from the character in the substring

In simpler terms, you need to find a run of exactly k identical consecutive characters that is either:

• At the beginning of the string (no character before it) or preceded by a different character
• At the end of the string (no character after it) or followed by a different character

For example:

• In string "aaabbb" with k = 3, the substring "aaa" satisfies all conditions (exactly 3 'a's, nothing before, 'b' after which is different)
• In string "xaaay" with k = 3, the substring "aaa" satisfies all conditions ('x' before which is different, 'y' after which is different)
• In string "aaaaa" with k = 3, there's no valid substring because any 3 consecutive 'a's would have another 'a' either before or after it

Return true if such a substring exists, otherwise return false.

Intuition

The key insight is that we're looking for segments of consecutive identical characters that have exactly length k. When we read the problem conditions carefully, we realize that a valid substring must be "isolated" - it can't be part of a longer sequence of the same character.

Think about it this way: if we have a string like "aaabbbcccc", the consecutive segments are:

• "aaa" (3 a's)
• "bbb" (3 b's)
• "cccc" (4 c's)

For each segment, if its length equals k, then it automatically satisfies all the conditions:

• It consists of only one repeated character ✓
• Any character before it (if exists) must be different, because otherwise it would be part of the same segment ✓
• Any character after it (if exists) must be different, for the same reason ✓

This leads us to a natural approach: instead of checking every possible substring of length k and verifying all conditions, we can simply identify all maximal segments of identical consecutive characters and check if any of them has length exactly k.

The two-pointer technique fits perfectly here. We use pointer l to mark the start of a segment, and pointer r to find where the segment ends (when we encounter a different character). The length of each segment is r - l. If this equals k, we've found our answer.

This approach is efficient because we only traverse the string once, and for each position, we immediately know if it's part of a valid segment or not.

Solution Approach

The solution uses a two-pointer technique to identify and measure consecutive segments of identical characters.

Algorithm Steps:

1. Initialize two pointers: l (left) starting at position 0, and n as the length of the string.

2. While l is within bounds (l < n):

   • Set r (right pointer) to start at the same position as l
   • Move r to the right as long as s[r] == s[l] (finding all consecutive identical characters)
   • When r stops, we have a complete segment from index l to r-1
   • Check if the segment length r - l equals k:
     • If yes, return true immediately (we found a valid substring)
     • If no, continue searching
   • Move l to position r (skip the entire processed segment)

3. If we've checked all segments and none has length k, return false

Why this works:

• When we find a segment where r - l == k, this segment automatically satisfies all conditions:
  • It consists of only one character (we only moved r while characters matched)
  • The character before index l (if exists) must be different, otherwise our segment would have started earlier
  • The character at index r (if exists) must be different, because that's why we stopped extending

Time Complexity: O(n) where n is the length of the string. Each character is visited at most twice (once by l and once by r).

Space Complexity: O(1) as we only use a constant amount of extra space for the pointers.

Example walkthrough with s = "aaabbb", k = 3:

• Start: l = 0, find segment "aaa" (r moves from 0 to 3)
• Check: 3 - 0 = 3, which equals k, so return true

Example Walkthrough

Let's trace through the algorithm with s = "aabbbaaa" and k = 3:

Step 1: Start with l = 0 (pointing to first 'a')

• Set r = 0
• Move r right while s[r] == s[0] (which is 'a')
• r moves: 0 → 1 → 2 (stops at index 2 because s[2] = 'b')
• Segment found: "aa" (from index 0 to 1)
• Check length: r - l = 2 - 0 = 2 ≠ 3
• Move l to r: l = 2

Step 2: Now l = 2 (pointing to first 'b')

• Set r = 2
• Move r right while s[r] == s[2] (which is 'b')
• r moves: 2 → 3 → 4 → 5 (stops at index 5 because s[5] = 'a')
• Segment found: "bbb" (from index 2 to 4)
• Check length: r - l = 5 - 2 = 3 = 3 ✓
• Return true - we found a valid substring!

The substring "bbb" satisfies all conditions:

• It has exactly length 3
• It consists of only 'b' characters
• The character before it ('a' at index 1) is different from 'b'
• The character after it ('a' at index 5) is different from 'b'

Another example with s = "aaaa" and k = 3:

Step 1: Start with l = 0

• Set r = 0
• Move r right while s[r] == s[0] (which is 'a')
• r moves: 0 → 1 → 2 → 3 → 4 (stops at index 4, end of string)
• Segment found: "aaaa" (entire string)
• Check length: r - l = 4 - 0 = 4 ≠ 3
• Move l to r: l = 4

Step 2: l = 4 which is ≥ n = 4, so exit loop

Return false - no segment of exactly length 3 exists. Even though "aaa" appears in the string, it's part of a longer run of 'a's, so it doesn't meet the isolation requirement.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm uses two pointers l and r to traverse the string. The outer while loop runs while l < n, and the inner while loop extends r to find consecutive identical characters. Although there are nested loops, each character in the string is visited at most twice - once when r passes over it and once when l is updated to r. The pointer l jumps directly to r after processing each group of identical characters, ensuring no character is processed redundantly. Therefore, the total number of operations is linear with respect to the string length.

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for the variables l, r, and n. No additional data structures are created that scale with the input size. The space usage remains constant regardless of the length of the input string s.

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

Common Pitfalls

Pitfall 1: Misunderstanding "Exactly k" Requirement

The Mistake: Developers often incorrectly check if a segment has at least k consecutive characters instead of exactly k. This leads to wrong answers when longer runs exist.

Incorrect Implementation:

# WRONG: This checks for "at least k" instead of "exactly k"
if right - left >= k:  # Bug: uses >= instead of ==
    return True

Why It Fails: For input s = "aaaaa", k = 3:

• The incorrect code would return True because it finds 5 consecutive 'a's (which is ≥ 3)
• But the correct answer is False because any substring of exactly 3 'a's has another 'a' adjacent to it

Correct Solution:

# CORRECT: Check for exactly k consecutive characters
if right - left == k:
    return True

Pitfall 2: Attempting Manual Boundary Checks

The Mistake: Some developers try to manually check if characters before and after differ, leading to complex and error-prone code:

# WRONG: Overly complex manual checking
for i in range(len(s) - k + 1):
    # Check if all k characters are the same
    if all(s[i] == s[j] for j in range(i, i + k)):
        # Manually check boundaries (error-prone!)
        before_ok = (i == 0 or s[i-1] != s[i])
        after_ok = (i + k == len(s) or s[i+k] != s[i])
        if before_ok and after_ok:
            return True

Why It's Problematic:

• More complex logic increases chance of bugs
• Inefficient: checks overlapping segments multiple times
• Harder to understand and maintain

Better Approach: The two-pointer method naturally handles boundaries because:

• When we identify a segment from left to right-1, the boundaries are automatically correct
• If there were more identical characters before left, our segment would have started earlier
• If there were more identical characters at right, we would have extended further

Pitfall 3: Off-by-One Errors with Segment Length

The Mistake: Confusion about whether right points to the last character in the segment or the first different character:

# WRONG: Misunderstanding what right represents
while right < string_length and s[right] == s[left]:
    right += 1
  
# Bug: Developer thinks segment length is right - left + 1
if right - left + 1 == k:  # WRONG!
    return True

Why It Fails: After the while loop, right points to either:

• The first character that's different from s[left], or
• string_length if we reached the end

The segment spans from index left to right-1, so its length is right - left, not right - left + 1.

Correct Understanding:

# After the while loop:
# - Segment starts at index: left
# - Segment ends at index: right - 1
# - Segment length: (right - 1) - left + 1 = right - left
if right - left == k:  # CORRECT
    return True