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 | 力扣

  • Tags: Array, Hash Table, Greedy, Sorting, Heap Priority Queue, Counting

2856. Minimum Array Length After Pair Removals

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Two Pointers, Binary Search, Greedy, Counting

1953. Maximum Number of Weeks for Which You Can Work

767. Reorganize String

  • LeetCode | 力扣

  • Tags: Hash Table, String, Greedy, Sorting, Heap Priority Queue, Counting

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 | 力扣

  • Tags: Array, Hash Table, Greedy, Sorting, Heap Priority Queue, Counting

import heapq
from collections import Counter, deque
from typing import List


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

    res = 0

    q = deque()

    while heap or q:
        res += 1

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

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

    return res


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

    max_exec = max(freq.values())
    max_count = sum(1 for v in freq.values() if v == max_exec)

    return max((max_exec - 1) * (n + 1) + max_count, len(tasks))


def test_least_interval_heap():
    assert least_interval_heap(["A", "A", "A", "B", "B", "B"], 2) == 8
    assert least_interval_heap(["A"], 0) == 1
    assert least_interval_heap(["A", "A", "A", "B", "B", "B"], 0) == 6
    assert least_interval_heap(["A", "A", "A", "A", "B", "B", "B", "C", "C"], 2) == 10


def test_least_interval_math():
    assert least_interval_math(["A", "A", "A", "B", "B", "B"], 2) == 8
    assert least_interval_math(["A"], 0) == 1
    assert least_interval_math(["A", "A", "A", "B", "B", "B"], 0) == 6
    assert least_interval_math(["A", "A", "A", "A", "B", "B", "B", "C", "C"], 2) == 10

358. Rearrange String k Distance Apart 👑

  • LeetCode | 力扣

  • Tags: Hash Table, String, Greedy, Sorting, Heap Priority Queue, Counting

984. String Without AAA or BBB

1405. Longest Happy String