lc

lc

# leetcode 347, description
# https://leetcode.com/problems/top-k-frequent-elements/
# simple description:
# Given an integer array nums and an integer k, return the k most frequent elements.

# heapq without nlargest
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        # Use a min-heap to keep track of the top k elements
        min_heap = []
        for num, freq in count.items():
            heapq.heappush(min_heap, (freq, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return [num for freq, num in min_heap]

# time complexity: O(n log k), where n is the number of elements in nums
# space complexity: O(n), for the Counter and the heap

# leetcode 1249, description
# https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/
# simple description:
# Given a string s of '(' , ')' and lowercase English characters.
# Your task is to remove the minimum number of parentheses (either '(' or ')', in any order) so that the resulting string is valid.
# Return any valid string as the answer.
# A string is valid if all parentheses are closed and matched.

def min_remove_to_make_valid(s: str) -> str:
    s = list(s)
    stack = []
    
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                s[i] = ''
                
    while stack:
        s[stack.pop()] = ''
        
    return ''.join(s)

def min_remove_to_make_valid2(s: str) -> str:
    S = list(s)
    open_count = 0
    
    # first pass: remove invalid ')'
    for i, char in enumerate(S):
        if char == '(':
            open_count += 1
        elif char == ')':
            if open_count:
                open_count -= 1
            else:
                S[i] = ''

    # second pass: remove invalid '('
    for i in range(len(S) - 1, -1, -1):
        if S[i] == '(' and open_count:
            S[i] = ''
            open_count -= 1

    return ''.join(S)

# leetcode 408, description
# https://leetcode.com/problems/valid-word-abbreviation/
# simple description:
# Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation

def valid_word_abbreviation(word: str, abbr: str) -> bool:
    wlen, alen = len(word), len(abbr)
    wi, ai = 0, 0
    while wi < wlen and ai < alen:
        if abbr[ai].isdigit():
            if abbr[ai] == '0':
                return False
            num = 0
            while ai < alen and abbr[ai].isdigit():
                num = num * 10 + int(abbr[ai])
                ai += 1
            wi += num
        else:
            if word[wi] != abbr[ai]:
                return False
            wi += 1
            ai += 1
    return wi == wlen and ai == alen

# leetcode 680
# https://leetcode.com/problems/valid-palindrome-ii/
# simple description:
# Given a string s, return true if the s can be palindrome after deleting at most one character from it.

def valid_palindrome(s: str) -> bool:
    def is_palindrome_range(left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Skip either the left or right character
            return is_palindrome_range(left + 1, right) or is_palindrome_range(left, right - 1)
        left += 1
        right -= 1
    return True