Welcome to Subscribe On Youtube

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

All Problems

All Solutions