LeetCode Problem 3456

Difficulty: 🟢 Easy
Topics: String

Solution

LeetCode 3456 - Find Special Substring of Length K

Problem Understanding

The problem gives us a string s and an integer k. We need to determine whether there exists a substring of length exactly k that satisfies three conditions.

First, every character inside the substring must be identical. In other words, the substring must consist of only one distinct character such as "aaa" or "bbbb".

Second, if there is a character immediately before the substring, that character must be different from the repeated character inside the substring.

Third, if there is a character immediately after the substring, that character must also be different from the repeated character inside the substring.

Another way to think about the problem is that we are looking for a contiguous block of identical characters whose length is exactly k. If the block were longer than k, then any length-k segment taken from inside that block would fail because it would have the same character immediately before or after it.

The input consists of:

• s, a lowercase English string.
• k, the required substring length.

The output is:

• true if at least one valid substring exists.
• false otherwise.

The constraints are very small:

• 1 <= k <= s.length <= 100

Since the string length is at most 100, even less efficient solutions would pass. However, it is still useful to develop the cleanest and most direct solution.

Important edge cases include:

• A valid substring appearing at the beginning of the string, where there is no left neighbor.
• A valid substring appearing at the end of the string, where there is no right neighbor.
• The entire string consisting of one repeated character.
• Runs of repeated characters longer than k, which should not count.
• The case k = 1, where a single isolated character may form a valid substring.

Approaches

Brute Force

A straightforward approach is to examine every possible substring of length k.

For each starting position, we extract the substring and verify:

1. All characters inside it are identical.
2. The character immediately before it, if it exists, is different.
3. The character immediately after it, if it exists, is different.

If any substring satisfies all conditions, we return true.

This approach is correct because it directly checks the definition of a valid substring. However, for every candidate substring we may need to scan up to k characters to verify that all characters are the same.

Key Insight

The important observation is that valid substrings correspond exactly to runs of identical characters whose length is exactly k.

Suppose we have a maximal run of some character:

aaaa

If the run length is exactly k, then the entire run forms a valid answer because both neighboring characters, if they exist, must be different.

If the run length is greater than k, then no length-k substring inside that run can be valid. Any such substring will have the same character immediately before or after it.

Therefore, instead of checking every length-k substring, we can scan the string and measure the length of each consecutive run of identical characters. If we ever find a run whose length equals k, we immediately return true.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Check every length-k substring individually
Optimal	O(n)	O(1)	Scan runs of identical characters once

Algorithm Walkthrough

1. Initialize an index i = 0 to start scanning the string.
2. While i is within the string, treat s[i] as the beginning of a run of identical characters.
3. Move another pointer j forward while s[j] is equal to s[i].
4. Once the run ends, compute its length as j - i.
5. If the run length is exactly k, return true. A maximal run of length exactly k automatically satisfies all boundary requirements because the characters outside the run, if they exist, are different.
6. Otherwise, move i to j and continue scanning the next run.
7. If the entire string is processed without finding a run of length exactly k, return false.

Why it works

The algorithm examines every maximal run of identical characters exactly once. A valid substring must consist entirely of one character and must not have the same character immediately before or after it. This is precisely the definition of a maximal run. Therefore, a valid substring exists if and only if there is a maximal run whose length is exactly k. Since every maximal run is checked, the algorithm is guaranteed to find a valid substring whenever one exists.

Python Solution

class Solution:
    def hasSpecialSubstring(self, s: str, k: int) -> bool:
        n = len(s)
        i = 0

        while i < n:
            j = i

            while j < n and s[j] == s[i]:
                j += 1

            if j - i == k:
                return True

            i = j

        return False

The implementation uses two pointers to identify consecutive runs of identical characters.

The outer loop processes one run at a time. For each run, i marks the start and j advances until a different character is found or the string ends.

The expression j - i gives the run length. If this length equals k, we immediately return True because that run satisfies all requirements.

After processing a run, we set i = j so the next iteration starts at the beginning of the next run.

If no qualifying run is found, the function returns False.

Go Solution

func hasSpecialSubstring(s string, k int) bool {
	n := len(s)
	i := 0

	for i < n {
		j := i

		for j < n && s[j] == s[i] {
			j++
		}

		if j-i == k {
			return true
		}

		i = j
	}

	return false
}

The Go implementation follows the same logic as the Python version. Since the string contains only lowercase English letters, indexing individual bytes is safe. No additional data structures are required, and all operations are performed in constant extra space.

Worked Examples

Example 1

Input

s = "aaabaaa"
k = 3

The runs are:

Run	Character	Start	End	Length
1	a	0	2	3
2	b	3	3	1
3	a	4	6	3

Execution:

i	j after scan	Run	Length	Result
0	3	"aaa"	3	length == k, return true

The algorithm returns true.

Example 2

Input

s = "abc"
k = 2

The runs are:

Run	Character	Length
a	1
b	1
c	1

Execution:

i	j after scan	Length	Match k?
0	1	1	No
1	2	1	No
2	3	1	No

No run has length 2, so the algorithm returns false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited once while scanning runs
Space	O(1)	Only a few integer variables are used

The two pointers move forward through the string without ever moving backward. Because each character belongs to exactly one run and is processed once, the total running time is linear in the length of the string.

Test Cases

sol = Solution()

assert sol.hasSpecialSubstring("aaabaaa", 3) is True      # provided example
assert sol.hasSpecialSubstring("abc", 2) is False         # provided example

assert sol.hasSpecialSubstring("a", 1) is True            # single character string
assert sol.hasSpecialSubstring("aaaa", 4) is True         # entire string is valid run
assert sol.hasSpecialSubstring("aaaa", 3) is False        # run longer than k

assert sol.hasSpecialSubstring("baaab", 3) is True        # valid run in middle
assert sol.hasSpecialSubstring("aaab", 3) is True         # valid run at beginning
assert sol.hasSpecialSubstring("baaa", 3) is True         # valid run at end

assert sol.hasSpecialSubstring("aabaa", 2) is True        # multiple valid runs
assert sol.hasSpecialSubstring("ababab", 1) is True       # isolated characters

assert sol.hasSpecialSubstring("bbbbbb", 1) is False      # no isolated character
assert sol.hasSpecialSubstring("bbbbbb", 6) is True       # whole string matches

assert sol.hasSpecialSubstring("aabbbcc", 3) is True      # middle run length k
assert sol.hasSpecialSubstring("aabbbcc", 2) is True      # another run length k
assert sol.hasSpecialSubstring("aabbbcc", 4) is False     # no run length k

assert sol.hasSpecialSubstring("abcccccde", 5) is True    # long run exactly k
assert sol.hasSpecialSubstring("abcccccde", 4) is False   # run exceeds k

Test Summary

Test	Why
"aaabaaa", 3	Provided example with valid run
"abc", 2	Provided example with no valid run
"a", 1	Smallest possible input
"aaaa", 4	Entire string forms the run
"aaaa", 3	Run longer than k should fail
"baaab", 3	Valid run surrounded by different characters
"aaab", 3	Run at beginning of string
"baaa", 3	Run at end of string
"aabaa", 2	Multiple valid runs exist
"ababab", 1	Isolated single-character runs
"bbbbbb", 1	No isolated character available
"bbbbbb", 6	Whole string is one valid run
"aabbbcc", 3	Middle run exactly matches k
"aabbbcc", 2	Different run matches k
"aabbbcc", 4	No run of required size
"abcccccde", 5	Long run exactly equal to k
"abcccccde", 4	Run longer than k should not count

Edge Cases

Entire String Is One Run

Consider:

s = "aaaa"
k = 4

A common mistake is to require both left and right neighbors to exist. In reality, missing neighbors are allowed. Since the entire string is a maximal run of length 4, it is a valid answer. The implementation correctly identifies the run length as 4 and returns true.

Run Longer Than K

Consider:

s = "aaaaa"
k = 3

A naive solution might notice that "aaa" appears inside the string and incorrectly return true. However, every length-3 substring is adjacent to another 'a', violating the boundary conditions. The implementation checks maximal run lengths, not arbitrary substrings, so it correctly returns false.

K Equals 1

Consider:

s = "abab"
k = 1

Each character forms a run of length 1. Since a maximal run length equals k, the answer is true. The implementation naturally handles this case because runs of length 1 are processed exactly like any other run length.

Valid Run at a Boundary

Consider:

s = "aaab"
k = 3

The valid substring is at the beginning of the string and has no left neighbor. The problem allows missing neighbors, so this should count. Because the algorithm operates on maximal runs rather than explicitly checking both sides, boundary runs are handled correctly without any special-case code.

Multiple Runs of Different Lengths

Consider:

s = "aabbbccccdd"
k = 2

Several runs exist, but only the first and last runs have length 2. The algorithm scans every maximal run and returns true as soon as it encounters a run whose length equals k, ensuring all possibilities are considered correctly.