20240530 2982 - Medium - SW

2982. Find Longest Special Substring That Occurs Thrice II

class Solution:
    def maximumLength(self, s: str) -> int:
        lenArrayMap = dict()
        charMaxLen = dict()
        
        for i in range(26):
            lenArrayMap[chr(ord("a")+i)] = [0 for _ in range(len(s)+1)]
        cnt = 0
        for i, c in enumerate(s):
            cnt += 1
            if i+1 == len(s) or c != s[i+1]:
                if c not in charMaxLen or charMaxLen[c] <= cnt:
                    charMaxLen[c] = cnt
                # print(i, c)
                cLenArray = lenArrayMap[c]
                for k in range(cnt):
                    # Add up the count of k len substring in current contiguous substring
                    cLenArray[k+1] += cnt - k
                cnt = 0
        
        res = -1
        for c in charMaxLen:
            maxLen = charMaxLen[c]
            lenArray = lenArrayMap[c]
            # print(c, maxLen, lenArray)
            for i in range(maxLen, 0, -1):
                if lenArray[i] >= 3:
                    if i > res:
                        res = i
                    break
        return res

Complexity

1. Time: O(n^2)
2. Space: O(n)