def lps(s: str) -> str:
    # your move 