Find the longest ordered substring in a string

longest_ordered_substring.py

from typing import Sequence, Tuple, TypeVar
from typing_extensions import Protocol


class SupportsGT(Protocol):
    def __gt__(self, other):
         ...


T = TypeVar('T', bound=SupportsGT)


def find_longest_ordered_subsequence(s: Sequence[T]) -> Sequence[T]:
    """ Find the longest ordered subsequence

    Supports any data type that implements '>' comparison
    """
    n = len(s)

    # initialize with the longest substring being just the first character
    # also, internally an inclusive range because that's easier to produce inside the loop
    best_len = 1
    best_range = (0, 0)

    for startpos in range(n):
        len_to_end = n - startpos

        if len_to_end < best_len:
            break

        # use the last character of the previous substring to efficiently check if the current substring is sorted:
        # all we have to do is compare the last character of the current string to the last
        # character of the prev string
        prev_last_char = ''

        # skip checking the substring s[0] since that's our base case
        min_offset = 1 if startpos == 0 else 0

        for curr_offset in range(min_offset, len_to_end):
            endpos = startpos + curr_offset  # inclusive end position
            curr_last_char = s[endpos]

            if prev_last_char > curr_last_char:
                break

            if curr_len > best_len:
                best_len = curr_len
                best_range = (startpos, endpos)

            prev_substring = current_substring

    best_substring = s[best_range[0] : best_range[1] + 1]
    return best_substring