
'''simple docstring'''
def 						UpperCamelCase_     (	__SCREAMING_SNAKE_CASE       ):
    """simple docstring"""






    snake_case_ :    Dict     			=						0

    # if input_string is "aba" than new_input_string become "a|b|a"
    snake_case_ :    Union[str, Any]     			=						""
    snake_case_ :    Union[str, Any]     			=						""

    # append each character + "|" in new_string for range(0, length-1)
    for i in input_string[: len(__SCREAMING_SNAKE_CASE       ) - 1]:
        new_input_string += i + "|"
    # append last character
    new_input_string += input_string[-1]

    # we will store the starting and ending of previous furthest ending palindromic
    # substring
    snake_case_ :    str     			=						0, 0

    # length[i] shows the length of palindromic substring with center i
    snake_case_ :    List[Any]     			=						[1 for i in range(len(__SCREAMING_SNAKE_CASE       )       )]

    # for each character in new_string find corresponding palindromic string
    snake_case_ :    str     			=						0
    for j in range(len(__SCREAMING_SNAKE_CASE       )       ):
        snake_case_ :    Any     			=						1 if j > r else min(length[l + r - j] // 2,		r - j + 1       )
        while (
            j - k >= 0
            and j + k < len(__SCREAMING_SNAKE_CASE       )
            and new_input_string[k + j] == new_input_string[j - k]
        ):
            k += 1

        snake_case_ :    Any     			=						2 * k - 1

        # does this string is ending after the previously explored end (that is r) ?
        # if yes the update the new r to the last index of this
        if j + k - 1 > r:
            snake_case_ :    str     			=						j - k + 1  # noqa: E741
            snake_case_ :    Dict     			=						j + k - 1

        # update max_length and start position
        if max_length < length[j]:
            snake_case_ :    str     			=						length[j]
            snake_case_ :    int     			=						j

    # create that string
    snake_case_ :    List[str]     			=						new_input_string[start - max_length // 2 : start + max_length // 2 + 1]
    for i in s:
        if i != "|":
            output_string += i

    return output_string


if __name__ == "__main__":
  import doctest

  doctest.testmod()






'''simple docstring'''
from __future__ import annotations

import math

def 						UpperCamelCase_     (	__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       ):
    """simple docstring"""






    if depth < 0:
        raise ValueError("Depth cannot be less than 0"       )

    if len(__SCREAMING_SNAKE_CASE       ) == 0:
        raise ValueError("Scores cannot be empty"       )

    if depth == height:
        return scores[node_index]

    if is_max:
        return max(
            minimax(depth + 1,		node_index * 2,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       ),		minimax(depth + 1,		node_index * 2 + 1,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       ),		)

    return min(
        minimax(depth + 1,		node_index * 2,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       ),		minimax(depth + 1,		node_index * 2 + 1,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       ),		)

def 						UpperCamelCase_     (	):
    """simple docstring"""






    snake_case_ :    int     			=						[9_0, 2_3, 6, 3_3, 2_1, 6_5, 1_2_3, 3_4_4_2_3]
    snake_case_ :    Union[str, Any]     			=						math.log(len(__SCREAMING_SNAKE_CASE       ),		2       )
    print("Optimal value : ",		end=""       )
    print(minimax(0,		0,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE,		__SCREAMING_SNAKE_CASE       )       )


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()




