2981. Find Longest Special Substring That Occurs Thrice I

leetcode_2981.java

/*
https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-i

2981. Find Longest Special Substring That Occurs Thrice I

Medium

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.
*/

import java.util.ArrayList;
class Solution {
    public int maximumLength(String s) {
        @SuppressWarnings("unchecked")
        ArrayList<int[]>[] a = new ArrayList[26];
        char prev_ch = s.charAt(0);
        char seq = 1;
        for (int i = 1; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == prev_ch) {
                seq++;
            } else {
                ArrayList<int[]> arr = a[prev_ch-'a'];
                if (arr == null) {
                    arr = new ArrayList<int[]>();
                    a[prev_ch-'a'] = arr;
                }
                int idx = bs(arr, seq);
                if (idx < arr.size() && arr.get(idx)[0] == seq) {
                    arr.get(idx)[1]++;
                } else {
                    arr.add(idx, new int[]{seq, 1});
                }
                seq = 1;
            }
            prev_ch = ch;
        }
        ArrayList<int[]> arr = a[prev_ch-'a'];
        if (arr == null) {
            arr = new ArrayList<>();
            a[prev_ch-'a'] = arr; 
        }
        int idx = bs(arr, seq);
        if (idx < arr.size() && arr.get(idx)[0] == seq) {
            arr.get(idx)[1]++;
        } else {
            arr.add(idx, new int[]{seq, 1});
        }
        int longest = -1;
        for (int i = 0; i < 26; i++) {
            arr = a[i];
            if (arr == null) {
                continue;
            }            
            for (int j = arr.size()-1; j >= 0; j--) {
                int[] pair = arr.get(j);
                int[] prev_pair = null;
                if (j > 0) {
                    prev_pair = arr.get(j-1);
                }
                if (pair[1] >= 3) {
                    longest = Math.max(longest, pair[0]);
                }

                if (pair[1] >= 2 && pair[0] >= 2) {
                    longest = Math.max(longest, pair[0]-1);
                }
                
                if (prev_pair != null && prev_pair[1]+(pair[0]-prev_pair[0]+1)*pair[1]>=3) {
                    longest = Math.max(longest, prev_pair[0]);
                }
                
                if (pair[0]>=3) {
                    longest = Math.max(longest, pair[0]-2);
                }
            }
        }
        return longest;
    }
    private int bs(ArrayList<int[]> a, int t_len) {
        int bad = -1;
        int good = a.size();
        while ((good - bad) > 1) {
            int m = bad + (good - bad)/2;
            int[] middle = a.get(m);
            if (middle[0] == t_len) {
                return m;
            }
            if (middle[0] < t_len) {
                bad = m;
            } else {
                good = m;
            }
        }
        return good;
    }
}

class Solution2 {
    public int maximumLength(String s) {
        PriorityQueue<Integer>[] a = new PriorityQueue[26];
        int fq = 1;
        char prev_ch = s.charAt(0);
        for (int i = 1; i < s.length(); i++) {
            char ch = s.charAt(i);
            PriorityQueue<Integer> pq = a[prev_ch-'a'];
            if (pq == null) {
                pq = new PriorityQueue<Integer>(
                    (Integer i1, Integer i2) -> Integer.compare(i1, i2)
                );
                a[prev_ch-'a'] = pq;
            }
            pq.offer(fq);
            if (pq.size()>3) {
                pq.poll();
            }
            if (ch == prev_ch) {
                fq++;
            } else {
                fq = 1;
                prev_ch = ch;
            }
        }
        PriorityQueue<Integer> pq = a[prev_ch-'a'];
        if (pq == null) {
            pq = new PriorityQueue<Integer>(
                (Integer i1, Integer i2) -> Integer.compare(i1, i2)
            );
            a[prev_ch-'a'] = pq;
        }
        pq.offer(fq);
        if (pq.size()>3) {
            pq.poll();
        }
        int result = -1;
        for (int i = 0; i < 26; i++) {
            pq = a[i];
            if (pq == null || pq.size() < 3) {
                continue;
            }
            result = Math.max(result, pq.peek());
        }
        return result;
    }
}