LC-0395 Medium LeetCode

395. Longest Substring with At Least K Repeating Characters

Hash Table String Divide and Conquer Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 45% Topics: Hash Table, String, Divide and Conquer, Sliding Window

Reading material

Arrays & Hashing 12 min Strings 12 min Divide & Conquer 11 min

Reference solution (spoiler · python)

# Time:  O(26 * n) = O(n)
# Space: O(26) = O(1)

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        def longestSubstringHelper(s, k, start, end):
            count = [0] * 26
            for i in xrange(start, end):
                count[ord(s[i]) - ord('a')] += 1
            max_len = 0
            i = start
            while i < end:
                while i < end and count[ord(s[i]) - ord('a')] < k:
                    i += 1
                j = i
                while j < end and count[ord(s[j]) - ord('a')] >= k:
                    j += 1

                if i == start and j == end:
                    return end - start

                max_len = max(max_len, longestSubstringHelper(s, k, i, j))
                i = j
            return max_len

        return longestSubstringHelper(s, k, 0, len(s))

Solution from kamyu104/LeetCode-Solutions · MIT