2981. Find Longest Special Substring That Occurs Thrice I

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.

C++

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

JAVA

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

PYTHON

• class Solution {
  public:
      int maximumLength(string s) {
          int n = s.size();
          int l = 0, r = n;
  
          // Lambda function to check if a length `x` satisfies the condition
          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) { // Condition for valid substring
                      return true;
                  }
                  i = j;
              }
              return false;
          };
  
          // Binary search for the maximum valid length
          while (l < r) {
              int mid = (l + r + 1) >> 1; // Right-biased midpoint
              if (check(mid)) {
                  l = mid; // Increase the length
              } else {
                  r = mid - 1; // Decrease the length
              }
          }
  
          return l == 0 ? -1 : l; // Return -1 if no valid length exists
      }
  };