from typing import Iterable
import re


def new_indexed_name(names: Iterable[str], pattern: str) -> str:
    """
    Return a new name that is unique in *names* and that conforms to *pattern*. The argument
    *pattern* must contain a single ``"{index}"`` substring.

    :param names: Sequence of names
    :param pattern: Naming pattern, e.g. "var_{index}"
    :return: a new name, e.g. "var_3"
    """
    if "{index}" not in pattern:
        raise ValueError('pattern must contain "{index}"')
    re_pattern = re.compile(pattern.replace("{index}", r"(\d+)"))
    max_index = 0
    for name in names:
        match_result = re_pattern.match(name)
        if match_result and match_result.group(1):
            max_index = max(max_index, int(match_result.group(1)))

    new_index = max_index + 1
    while True:
        new_name = pattern.replace("{index}", str(new_index))
        if not new_name.isidentifier():
            raise ValueError('pattern does not yield a valid name')
        if new_name not in names:
            return new_name
        new_index += 1