LeetCodeWeekly238C: 1839. Longest Substring Of All Vowels in Order 区間操作 一定の文字出現する最大の単調増加文字列

題意(オリジナル)

• 英語小文字の集合である文字列$s$が与えられる．
• 良い文字列を以下のように定義する．ソートされた$x$文字の連続した文字列であり、この中に$a,i,u,e,o$の５文字が１回以上出現していなければならない．
• この文字列の長さの最大長を求めよ

こう考えた

簡単のため、問題文を以下のように言い換える．

• $|s|$の配列$a$が与えられ、各要素 $a_i$は $0 \leq a_i \leq 25$である
• よい区間とは以下の通りである．連続した区間の要素が全てソートされており（つまり、単調増加）、この中に$0, 8, 20, 4, 15$が1度以上含まれている

ここで、連続した区間とは、ある任意の $ 0 \leq l \leq r < |s| $と言い換えられる．さて、ここで単調増加である条件を考えると、ある$l$を固定した際、$r$を右に伸ばしていき、伸ばせるところまで伸ばし、その中に、$0, 8, 20, 4, 15$が含まれているならばそれは最長の長さの候補として扱える．

このため、以下のように判定をする．

• l = 0からスタートし、単調増加で有る限り、rをインクリメントする
• 単調増加でなくなった場合、今の区間に必要な文字が含まれているかを判定する．
• Yesの場合、その文字長を候補とする．Noの場合、捨てる

実装

特に留意点はなし．工夫は以下程度．

• 先に$s$は数値のリストにしておく方が良い

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        judge = lambda : cnt[0]!=0 and cnt[8]!=0 and cnt[20]!=0 and cnt[4]!=0 and cnt[14]!=0
        chr2int = lambda x: ord(x) - ord("a")
        s,l,r = word,0,0
        s = list(map(chr2int, s))
        cnt = [0] * 26
        res = 0
        p = -1
        while r < len(s):
            cnt[s[r]] += 1
            # 足した文字が条件を達成しているか？
            if s[r] < p:
                l = r
                r += 1
                p = s[r]
                continue
            p = s[r]
            if judge(): # 文字が足りている
                res = max(res, (r-l) + 1)
            r += 1
        return res