





from timeit import timeit

_UpperCAmelCase				:       Union[str, Any]	   =				{
    """MALAYALAM""": True,
    """String""": False,
    """rotor""": True,
    """level""": True,
    """A""": True,
    """BB""": True,
    """ABC""": False,
    """amanaplanacanalpanama""": True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     bool:
    lowerCamelCase__    :      Tuple					 =		0
    lowerCamelCase__    :      Dict					 =		len(_UpperCAmelCase ) - 1
    while start_i < end_i:
        if s[start_i] == s[end_i]:
            start_i += 1
            end_i -= 1
        else:
            return False
    return True


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     bool:
    lowerCamelCase__    :      Dict					 =		len(_UpperCAmelCase ) // 2
    lowerCamelCase__    :      Tuple					 =		len(_UpperCAmelCase )

    # We need to traverse till half of the length of string
    # as we can get access of the i'th last element from
    # i'th index.
    # eg: [0,1,2,3,4,5] => 4th index can be accessed
    # with the help of 1st index (i==n-i-1)
    # where n is length of string
    return all(s[i] == s[n - i - 1] for i in range(_UpperCAmelCase ) )


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     bool:
    if len(_UpperCAmelCase ) <= 2:
        return True
    if s[0] == s[len(_UpperCAmelCase ) - 1]:
        return is_palindrome_recursive(s[1:-1] )
    else:
        return False


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     bool:
    return s == s[::-1]


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     None:
    lowerCamelCase__    :      Any					 =		F"""all({name}(key) is value for key, value in test_data.items())"""
    lowerCamelCase__    :      List[Any]					 =		F"""from __main__ import test_data, {name}"""
    lowerCamelCase__    :      int					 =		50_0000
    lowerCamelCase__    :      List[str]					 =		timeit(stmt=_UpperCAmelCase						,	setup=_UpperCAmelCase						,	number=_UpperCAmelCase )
    print(F"""{name:<35} finished {number:,} runs in {result:.5f} seconds""" )


if __name__ == "__main__":
    for key, value in test_data.items():
        assert is_palindrome(key) is is_palindrome_recursive(key)
        assert is_palindrome(key) is is_palindrome_slice(key)
        print(F"""{key:21} {value}""")
    print("""a man a plan a canal panama""")

    # finished 500,000 runs in 0.46793 seconds
    benchmark_function("""is_palindrome_slice""")
    # finished 500,000 runs in 0.85234 seconds
    benchmark_function("""is_palindrome""")
    # finished 500,000 runs in 1.32028 seconds
    benchmark_function("""is_palindrome_recursive""")
    # finished 500,000 runs in 2.08679 seconds
    benchmark_function("""is_palindrome_traversal""")












from __future__ import annotations

from typing import Any


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     None:
    create_state_space_tree(_UpperCAmelCase						,	[]						,	0 )


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase						,	_UpperCAmelCase						,	_UpperCAmelCase )			->     None:

    if index == len(_UpperCAmelCase ):
        print(_UpperCAmelCase )
        return

    create_state_space_tree(_UpperCAmelCase						,	_UpperCAmelCase						,	index + 1 )
    current_subsequence.append(sequence[index] )
    create_state_space_tree(_UpperCAmelCase						,	_UpperCAmelCase						,	index + 1 )
    current_subsequence.pop()


if __name__ == "__main__":
    _UpperCAmelCase				:       list[Any]	   =				[3, 1, 2, 4]
    generate_all_subsequences(seq)

    seq.clear()
    seq.extend(["""A""", """B""", """C"""])
    generate_all_subsequences(seq)





