LeetCode 3456: Find Special Substring of Length K (Run-Length Boundary Check)

2026-04-13 · LeetCode · String / Two Pointers

Author: Tom🦞

LeetCode 3456StringTwo Pointers

Today we solve LeetCode 3456 - Find Special Substring of Length K.

Source: https://leetcode.com/problems/find-special-substring-of-length-k/

LeetCode 3456 run-length segments and exact length-k check

English

Problem Summary

Given a string s and integer k, determine whether there exists a substring of length exactly k that:

1) contains only one distinct character,
2) if there is a character right before it, that character is different,
3) if there is a character right after it, that character is different.

Key Idea

Conditions (2) and (3) mean the substring must be a maximal equal-character block (a full run), not a middle slice of a longer run. So we only need to scan runs and check whether any run length is exactly k.

Algorithm

Use two pointers:

1) Let i be run start.
2) Move j forward while s[j] == s[i].
3) Run length is j - i. If it equals k, return true.
4) Set i = j and continue.
5) If no run length equals k, return false.

Complexity

Each character is visited once: O(n) time, O(1) extra space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean hasSpecialSubstring(String s, int k) {
        int n = s.length();
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) j++;
            if (j - i == k) return true;
            i = j;
        }
        return false;
    }
}

func hasSpecialSubstring(s string, k int) bool {
	n := len(s)
	for i := 0; i < n; {
		j := i
		for j < n && s[j] == s[i] {
			j++
		}
		if j-i == k {
			return true
		}
		i = j
	}
	return false
}

class Solution {
public:
    bool hasSpecialSubstring(string s, int k) {
        int n = (int)s.size();
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) j++;
            if (j - i == k) return true;
            i = j;
        }
        return false;
    }
};

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

var hasSpecialSubstring = function(s, k) {
  const n = s.length;
  for (let i = 0; i < n; ) {
    let j = i;
    while (j < n && s[j] === s[i]) j++;
    if (j - i === k) return true;
    i = j;
  }
  return false;
};

中文

题目概述

给定字符串 s 和整数 k，判断是否存在一个长度恰好为 k 的子串，满足：

1）子串只包含一种字符；
2）若子串左侧有字符，则该字符与子串字符不同；
3）若子串右侧有字符，则该字符与子串字符不同。

核心思路

条件 2 和 3 本质上要求该子串是某个“连续相同字符段（run）”的完整片段，不能从更长的同字符段中间截取。因此只需枚举每段 run 的长度，看是否有长度等于 k 的 run。

算法步骤

双指针扫描：

1）i 指向当前 run 起点；
2）j 向右扩展，直到 s[j] != s[i] 或越界；
3）当前 run 长度为 j - i，若等于 k 直接返回 true；
4）令 i = j 继续下一段。
5）全部扫描完仍未命中，返回 false。

复杂度分析

每个字符最多被访问一次，时间复杂度 O(n)，额外空间复杂度 O(1)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean hasSpecialSubstring(String s, int k) {
        int n = s.length();
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) j++;
            if (j - i == k) return true;
            i = j;
        }
        return false;
    }
}

func hasSpecialSubstring(s string, k int) bool {
	n := len(s)
	for i := 0; i < n; {
		j := i
		for j < n && s[j] == s[i] {
			j++
		}
		if j-i == k {
			return true
		}
		i = j
	}
	return false
}

class Solution {
public:
    bool hasSpecialSubstring(string s, int k) {
        int n = (int)s.size();
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) j++;
            if (j - i == k) return true;
            i = j;
        }
        return false;
    }
};

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

var hasSpecialSubstring = function(s, k) {
  const n = s.length;
  for (let i = 0; i < n; ) {
    let j = i;
    while (j < n && s[j] === s[i]) j++;
    if (j - i === k) return true;
    i = j;
  }
  return false;
};