from typing import Any
import random


def assign_new_ids(items: dict[str, Any]) -> list[str]:
    """
    Assigns new IDs to any item ID that starts with "NEW:" or is an empty
    string. Will modify the dict in place. Will return a list of new item IDs
    assigned.
    """
    new_items = []
    for item_id in items:
        if item_id in ('', 'NEW') or item_id.startswith('NEW:'):
            new_items.append(item_id)

    for i, item_id in enumerate(new_items):
        item_range = (10 ** (max(len(str(len(items))), 5) + 1)) - 1
        item_range_l = len(str(item_range))
        new_id: str = ''
        while not new_id or new_id in items:
            new_id = str(random.randint(0, item_range)).zfill(item_range_l)
        items[new_id] = items.pop(item_id)
        new_items[i] = new_id

    return new_items