Question

2982. Find Longest Special Substring That Occurs Thrice II

中文文档

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 <= 5 * 105
• 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$.

The time complexity is $O((n + |\Sigma|) \times \log n)$, and the space complexity is $O(|\Sigma|)$, where $n$ is the length of the string $s$, and $|\Sigma|$ represents the size of the character set. In this problem, the character set is lowercase English letters, so $|\Sigma| = 26$.

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;
}