Longest Alphabetical Subsequence

You are given a string s. Your task is to determine the length of the longest subsequence of s in which the characters appear in non-decreasing alphabetical order. A subsequence is a sequence that can be derived from the original string by deleting some or no elements without changing the order of the remaining characters.

For example, given s = "abac", one possible longest alphabetical subsequence is "abc", which has length 3. Note that the characters in the subsequence need not be contiguous in the original string.

The expected time complexity of a straightforward solution is \(O(n^2)\), where \(n\) is the length of the input string.

inputFormat

The input consists of a single line containing the string s.

Note: The string may include lowercase letters; it may be empty as well.

outputFormat

Output a single integer representing the length of the longest subsequence in which the letters are in non-decreasing alphabetical order.

abac

3