23.06.12 Today’s Leetcode

228. Summary Ranges (easy)

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        i = 0
        n = len(nums)
        res = list()
        while i < n:
            j = i
            while j + 1 < n and nums[j + 1] - nums[j] == 1:
                j += 1
            
            temp = str(nums[i])
            if j > i:
                temp += '->'
                temp += str(nums[j])
            res.append(temp)
            i = j + 1
        return res

214. Shortest Palindrome (hard)

class Solution:
    def shortestPalindrome(self, s: str) -> str:

        def isPalindrome(s):
            return s == s[::-1]

        n = len(s)
        for i in range(n, -1, -1):
            temp = s[:i]
            if isPalindrome(temp):
                return s[i:][::-1] + s
        return ''

similar with my solution, but it start from center, n // 2

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        center = len(s) // 2
        while center >= 0:
            left, right = center - 1, center + 1
            while left >= 0 and s[left] == s[center]:
                left -= 1
            while right < len(s) and s[right] == s[center]:
                right += 1
            center = left
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left, right = left - 1, right + 1
            if left == -1:
                return s[right:][::-1] + s

368. Largest Divisible Subset

class Solution:

    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        # We'll traverse values in nums in ascending order
        nums.sort()
        # Ordered (by length) list of valid subsets that are largest subset candidates
        subsets = []
        
        # Add max-length subset for each value
        for i, num in enumerate(nums):
            # Find the biggest subset we can add num to, and add this new subset to subsets (maintaining order)
            for j in range(i - 1, -1, -1):
                # If satisfies divisibility, insert into subsets (as per size, 1 bigger than previous subset)
                if not num % subsets[j][-1]:
                    # Location of where to insert new extended subset (Alt.: Could binary search for it)
                    k = next(filter(lambda k: len(subsets[j]) != len(subsets[k]), range(j + 1, i)), i)
                    subsets.insert(k, subsets[j] + [num])
                    break
            else:
                # num can't be added as an extension to any subset, create a blank one for it
                subsets.insert(0, [num])

        return subsets[-1]

395. Longest Substring with At Least K Repeating Characters (medium)

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        def check(c):
            res = set()
            for key, value in c.items():
                if value >= k or value == 0:
                    continue
                else:
                    res.add(key)
            return res

        n = len(s)
        temp = check(Counter(s))
        print(temp)
        if not temp:
            return n

        prev = res = 0
        counter = Counter()
        for i, v in enumerate(s):
            if v in temp:
                if not check(counter):
                    res = max(res, prev)
                counter = Counter()
                prev = 0
            else:
                counter[v] += 1
                prev += 1

        if not check(counter):
            res = max(res, prev)
        return res

divide and conquer

class Solution:

    def rec(self,s,k):
        #s += '0' will lead to infinite loop
        # eg "aaa0" will always be checked, s[0:3]->s[0:3]  
        #so on
        hmap = defaultdict(int);
        for c in s: hmap[c] += 1
        p, res = -1, 0
        for i in range(len(s)):
            if(hmap[s[i]] < k):
                res = max(res, self.rec(s[p + 1:i], k))
                p = i

        if(p > -1):
            res = max(res,self.rec(s[p + 1:len(s)], k))
        
        if(p == -1): return len(s);
        else: return res 
        
    def longestSubstring(self, s: str, k: int) -> int:
        return self.rec(s,k)