Skip to content

Adjacent Different

Table of Contents

2335. Minimum Amount of Time to Fill Cups

1753. Maximum Score From Removing Stones

1054. Distant Barcodes

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, greedy, sorting, heap priority queue, counting

2856. Minimum Array Length After Pair Removals

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, two pointers, binary search, greedy, counting

1953. Maximum Number of Weeks for Which You Can Work

767. Reorganize String

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, greedy, sorting, heap priority queue, counting

767. Reorganize String - Python Solution
import heapq
from collections import Counter


def reorganizeString(s: str) -> str:
    if not s:
        return ""

    heap = [(-freq, char) for char, freq in Counter(s).items()]  # max heap
    heapq.heapify(heap)

    result = []
    prev_count, prev_char = 0, ""

    while heap:
        count, char = heapq.heappop(heap)  # pop the most frequent character
        result.append(char)  # append the character to the result

        if (
            prev_count < 0
        ):  # if the previous character still has remaining count
            heapq.heappush(heap, (prev_count, prev_char))

        prev_count = (
            count + 1
        )  # update the current character's remaining count
        prev_char = char  # update the current character

    # check if there is any invalid result
    if len(result) != len(s):
        return ""

    return "".join(result)


print(reorganizeString("aab"))

3139. Minimum Cost to Equalize Array

621. Task Scheduler

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, greedy, sorting, heap priority queue, counting

621. Task Scheduler - Python Solution
import heapq
from collections import Counter, deque
from typing import List


# Heap
def leastInterval1(tasks: List[str], n: int) -> int:
    count = Counter(tasks)
    heap = [-c for c in count.values()]
    heapq.heapify(heap)

    time = 0

    q = deque()

    while heap or q:
        time += 1

        if heap:
            cnt = 1 + heapq.heappop(heap)
            if cnt:
                q.append((cnt, time + n))

        if q and q[0][1] == time:
            heapq.heappush(heap, q.popleft()[0])

    return time


def leastInterval2(tasks: List[str], n: int) -> int:
    freq = Counter(tasks)

    maxExec = max(freq.values())
    maxCount = sum(1 for v in freq.values() if v == maxExec)

    return max((maxExec - 1) * (n + 1) + maxCount, len(tasks))


tasks = ["A", "A", "A", "B", "B", "B"]
n = 2
print(leastInterval1(tasks, n))  # 8
print(leastInterval2(tasks, n))  # 8

358. Rearrange String k Distance Apart

  • LeetCode | LeetCode CH (Hard)

  • Tags: hash table, string, greedy, sorting, heap priority queue, counting

984. String Without AAA or BBB

1405. Longest Happy String

Comments