LC-2982 Medium LeetCode

2982. Find Longest Special Substring That Occurs Thrice II

Hash Table String Binary Search Sliding Window Counting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 38% Topics: Hash Table, String, Binary Search, Sliding Window, Counting

Reading material

Arrays & Hashing 12 min Strings 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(26 * 3 + n * 3)
# Space: O(26 * 3)

# string, hash table
class Solution(object):
    def maximumLength(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup = [[0]*3 for _ in xrange(26)]
        result = cnt = 0
        for i, c in enumerate(s):
            cnt += 1
            if i+1 != len(s) and s[i+1] == s[i]:
                continue
            curr = lookup[ord(c)-ord('a')]
            for j in xrange(len(curr)):
                if curr[j] < cnt:
                    cnt, curr[j] = curr[j], cnt
            cnt = 0
            result = max(result, max(curr[0]-2, min(curr[0]-1, curr[1]), curr[2]))
        return result if result else -1

Solution from kamyu104/LeetCode-Solutions · MIT