Leetcode 1122 Solution

This article provides solution to leetcode question 1122 (longest-duplicate-substring)
Categories:
Tags:
Access this page by simply typing in "lcs 1122" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/longest-duplicate-substring

Solution

import collections

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        def get_duplicate_substr(k):
            counters = collections.defaultdict(int)

            for i in range(k - 1, len(s)):
                ss = s[i + 1 - k:i + 1]
                counters[ss] += 1

            left_keys = [k for k, v in counters.items() if v > 1]
            return left_keys[0] if left_keys else ""

        l = 1
        r = len(s) - 1

        while l < r:
            m = (l + r + 1) // 2
            if get_duplicate_substr(m) != "":
                l = m
            else:
                r = m - 1

        return get_duplicate_substr(l)