3456. Find Special Substring of Length K

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:

The substring consists of only one distinct character (e.g., "aaa" or "bbb").
If there is a character immediately before the substring, it must be different from the character in the substring.
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.

Example 1:

Input: s = "aaabaaa", k = 3

Output: true

Explanation:

The substring s[4..6] == "aaa" satisfies the conditions.

It has a length of 3.
All characters are the same.
The character before "aaa" is 'b', which is different from 'a'.
There is no character after "aaa".

Example 2:

Input: s = "abc", k = 2

Output: false

Explanation:

There is no substring of length 2 that consists of one distinct character and satisfies the conditions.

Constraints:

1 <= k <= s.length <= 100
s consists of lowercase English letters only.

Solutions

Solution 1: Two Pointers

Thinking

A special substring is a run of one letter whose length is exactly \(k\), not a piece of a longer run. \(|s|\le 100\), so a run-length scan is enough.

A window of length \(k\) would accept a slice of a longer identical run when both ends match.

Two pointers isolate each constant run and succeed only when the run length equals \(k\).

The problem essentially asks us to find each segment of consecutive identical characters and then determine if there exists a substring of length \(k\). If such a substring exists, return \(\textit{true}\); otherwise, return \(\textit{false}\).

We can use two pointers \(l\) and \(r\) to traverse the string \(s\). When \(s[l] = s[r]\), move \(r\) to the right until \(s[r] \neq s[l]\). At this point, check if \(r - l\) equals \(k\). If it does, return \(\textit{true}\); otherwise, move \(l\) to \(r\) and continue traversing.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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

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

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

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

function hasSpecialSubstring(s: string, k: number): boolean {
    const n = s.length;
    for (let l = 0; l < n;) {
        let r = l + 1;
        while (r < n && s[r] === s[l]) {
            r++;
        }
        if (r - l === k) {
            return true;
        }
        l = r;
    }
    return false;
}

3456. Find Special Substring of Length K

Description

Solutions

Solution 1: Two Pointers

Comments