from typing import Dict
from typing import List


def _reconstruct_optimal_alignment(
    x: str, y: str, a: int, b: int, pen_gap: Dict[str, Dict[str, int]],
    dp: List[List[int]], sx_ends_with_gap: List[List[bool]],
    sy_ends_with_gap: List[List[bool]]
) -> List[str]:
    """
    Private helper function to reconstruct the optimal alignment according to
    the optimal solution using backtracking.
    :param x: str
    :param y: str
    :param a: int
    :param b: int
    :param pen_gap: dict{str: dict{str: int}}
    :param dp: list[list[int]]
    :param sx_ends_with_gap: list[list[bool]]
    :param sy_ends_with_gap: list[list[bool]]
    :return: list[str]
    """
    sx, sy = '', ''
    i, j = len(x), len(y)
    while i >= 1 and j >= 1:
        x_curr, y_curr = x[i - 1], y[j - 1]
        result1 = dp[i - 1][j - 1] + pen_gap[x_curr][y_curr]
        result2 = dp[i - 1][j] + a
        if not sx_ends_with_gap[i - 1][j]:
            result2 += b
        result3 = dp[i][j - 1] + a
        if not sy_ends_with_gap[i][j - 1]:
            result3 += b
        result = min(result1, result2, result3)
        if result == result1:
            # Case 1: The final positions are x_i and y_j.
            sx = x_curr + sx
            sy = y_curr + sy
            i -= 1
            j -= 1
        elif result == result2:
            # Case 2: The final positions are x_i and a gap.
            sx = x_curr + sx
            sy = ' ' + sy
            i -= 1
        else:
            # Case 3: The final positions are a gap and y_j.
            sx = ' ' + sx
            sy = y_curr + sy
            j -= 1
    if i:
        sy = ' ' * i + sy
    else:
        sx = ' ' * j + sx
    return [sx, sy]
    # Running time complexity: O(m + n)