def lps_naive(sequence: str, start: int, end: int) -> int:
    """
    LPS(i, j) = LPS(i+1, j-1) + 2, if sequence[i] == sequence[j] or i+1 == j-1
              = max(LPS(i+1, j), LPS(i, j-1)), if sequence[i] != sequence[j]
    """
    if start > end:
        return 0

    if start == end:
        return 1

    if start == end - 1 and sequence[start] == sequence[end]:
        return 2

    if sequence[start] == sequence[end]:
        return 2 + lps_naive(sequence, start + 1, end - 1)

    return max(lps_naive(sequence, start + 1, end), lps_naive(sequence, start, end - 1))