LC-3035 Medium LeetCode

3035. Maximum Palindromes After Operations

Array Hash Table String Greedy Sorting Counting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 43% Topics: Array, Hash Table, String, Greedy, Sorting, Counting

Reading material

Arrays & Hashing 12 min Strings 12 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n * l + nlogn)
# Space: O(n)

# freq table, greedy, sort
class Solution(object):
    def maxPalindromesAfterOperations(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        cnt = [0]*26
        for w in words:
            for c in w:
                cnt[ord(c)-ord('a')] += 1
        curr = sum(x//2 for x in cnt)
        for i, l in enumerate(sorted(map(len, words))):
            curr -= l//2
            if curr < 0:
                return i
        return len(words)

Solution from kamyu104/LeetCode-Solutions · MIT