Find Longest Special Substring That Occurs Thrice I

Leetcode Problem:

• Find Longest Special Substring That Occurs Thrice I

Summary

• Find the length of the longest special substring of a given string that occurs at least thrice, or return -1 if no such substring exists.

Approach

• Use binary search to find the longest special substring that occurs at least thrice
• The approach involves checking for the presence of a special character (a single character) in the string and counting its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings.

Complexity

• O(n log m) where n is the length of the string and m is the range of possible special characters (26 lowercase English letters)

Explanation

• The solution uses binary search to efficiently find the longest special substring that occurs at least thrice
• The binary search range is initially set to the entire string, and the approach iteratively narrows down the range to focus on longer special substrings
• The approach checks for the presence of a special character in the string and counts its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings
• The process is repeated until the longest special substring that occurs at least thrice is found, or the binary search range becomes empty.

Solution Code:

class Solution {
public:
    int maximumLength(string s) {
        int ans = -1;
        int l = 1;
        int r = s.size()-2;
        
        while(l <= r){
            int mid = (l + r) >> 1;
            bool success = false;
            for(char i = 'a'; i <= 'z'; i++){
                int k = 0;
                int specialCnt = 0;
                for(int j = 0; j < s.size(); j++){
                    if(s[j] == i){
                        k++;
                    } else{
                        k = 0;
                    }
                    if(k == mid){
                        k--;
                        specialCnt++;
                        if(specialCnt >= 3){
                            success = true;
                            break;
                        }
                    }
                }
                if(success) break;
            }
            if(success){
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};