2981. Find Longest Special Substring That Occurs Thrice I

Description

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

Constraints:

3 <= s.length <= 50
s consists of only lowercase English letters.

Solutions

Solution 1: Binary Search + Sliding Window Counting

We notice that if there exists a special substring of length \(x\) that appears at least three times, then a special substring of length \(x-1\) must also exist. This exhibits a monotonicity, so we can use binary search to find the longest special substring.

We define the left boundary of the binary search as \(l = 0\) and the right boundary as \(r = n\), where \(n\) is the length of the string. In each binary search, we take \(mid = \lfloor \frac{l + r + 1}{2} \rfloor\). If a special substring of length \(mid\) exists, we update the left boundary to \(mid\). Otherwise, we update the right boundary to \(mid - 1\). During the binary search, we use a sliding window to count the number of special substrings.

Specifically, we design a function \(check(x)\) to indicate whether a special substring of length \(x\) that appears at least three times exists.

In the function \(check(x)\), we define a hash table or an array of length \(26\) named \(cnt\), where \(cnt[i]\) represents the count of special substrings of length \(x\) composed of the \(i\)-th lowercase letter. We traverse the string \(s\). If the current character is \(s[i]\), we move the pointer \(j\) to the right until \(s[j] \neq s[i]\). At this point, \(s[i \cdots j-1]\) is a special substring of length \(x\). We increase \(cnt[s[i]]\) by \(\max(0, j - i - x + 1)\), and then update the pointer \(i\) to \(j\).

After the traversal, we go through the array \(cnt\). If there exists \(cnt[i] \geq 3\), it means a special substring of length \(x\) that appears at least three times exists, so we return \(true\). Otherwise, we return \(false\).

Python3JavaC++GoTypeScript

class Solution:
    def maximumLength(self, s: str) -> int:
        def check(x: int) -> bool:
            cnt = defaultdict(int)
            i = 0
            while i < n:
                j = i + 1
                while j < n and s[j] == s[i]:
                    j += 1
                cnt[s[i]] += max(0, j - i - x + 1)
                i = j
            return max(cnt.values()) >= 3

        n = len(s)
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return -1 if l == 0 else l

class Solution {
    private String s;
    private int n;

    public int maximumLength(String s) {
        this.s = s;
        n = s.length();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }

    private boolean check(int x) {
        int[] cnt = new int[26];
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int k = s.charAt(i) - 'a';
            cnt[k] += Math.max(0, j - i - x + 1);
            if (cnt[k] >= 3) {
                return true;
            }
            i = j;
        }
        return false;
    }
}

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        int l = 0, r = n;
        auto check = [&](int x) {
            int cnt[26]{};
            for (int i = 0; i < n;) {
                int j = i + 1;
                while (j < n && s[j] == s[i]) {
                    ++j;
                }
                int k = s[i] - 'a';
                cnt[k] += max(0, j - i - x + 1);
                if (cnt[k] >= 3) {
                    return true;
                }
                i = j;
            }
            return false;
        };
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l == 0 ? -1 : l;
    }
};

func maximumLength(s string) int {
    n := len(s)
    l, r := 0, n
    check := func(x int) bool {
        cnt := [26]int{}
        for i := 0; i < n; {
            j := i + 1
            for j < n && s[j] == s[i] {
                j++
            }
            k := s[i] - 'a'
            cnt[k] += max(0, j-i-x+1)
            if cnt[k] >= 3 {
                return true
            }
            i = j
        }
        return false
    }
    for l < r {
        mid := (l + r + 1) >> 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    if l == 0 {
        return -1
    }
    return l
}

function maximumLength(s: string): number {
    const n = s.length;
    let [l, r] = [0, n];
    const check = (x: number): boolean => {
        const cnt: number[] = Array(26).fill(0);
        for (let i = 0; i < n; ) {
            let j = i + 1;
            while (j < n && s[j] === s[i]) {
                j++;
            }
            const k = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
            cnt[k] += Math.max(0, j - i - x + 1);
            if (cnt[k] >= 3) {
                return true;
            }
            i = j;
        }
        return false;
    };
    while (l < r) {
        const mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l === 0 ? -1 : l;
}

Solution 2: Counting

The time complexity is \(O(n)\)

TypeScriptJavaScript

function maximumLength(s: string): number {
    const cnt = new Map<string, number>();
    const n = s.length;
    let [c, ch] = [0, ''];

    for (let i = 0; i < n + 1; i++) {
        if (ch === s[i]) {
            c++;
        } else {
            let j = 1;
            while (c) {
                const char = ch.repeat(j++);
                cnt.set(char, (cnt.get(char) ?? 0) + c);
                c--;
            }

            ch = s[i];
            c = 1;
        }
    }

    let res = -1;
    for (const [x, c] of cnt) {
        if (c >= 3) {
            res = Math.max(res, x.length);
        }
    }

    return res;
}

function maximumLength(s) {
    const cnt = new Map();
    const n = s.length;
    let [c, ch] = [0, ''];

    for (let i = 0; i < n + 1; i++) {
        if (ch === s[i]) {
            c++;
        } else {
            let j = 1;
            while (c) {
                const char = ch.repeat(j++);
                cnt.set(char, (cnt.get(char) ?? 0) + c);
                c--;
            }

            ch = s[i];
            c = 1;
        }
    }

    let res = -1;
    for (const [x, c] of cnt) {
        if (c >= 3) {
            res = Math.max(res, x.length);
        }
    }

    return res;
}

2981. Find Longest Special Substring That Occurs Thrice I

Description

Solutions

Solution 1: Binary Search + Sliding Window Counting

Solution 2: Counting

Comments