LeetCodeWeekly238C: 1839. Longest Substring Of All Vowels in Order 区間操作 一定の文字出現する最大の単調増加文字列
題意(オリジナル)
- 英語小文字の集合である文字列$s$が与えられる.
- 良い文字列を以下のように定義する.ソートされた$x$文字の連続した文字列であり、この中に$a,i,u,e,o$の5文字が1回以上出現していなければならない.
- この文字列の長さの最大長を求めよ
こう考えた
簡単のため、問題文を以下のように言い換える.
- $|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
Author And Source
この問題について(LeetCodeWeekly238C: 1839. Longest Substring Of All Vowels in Order 区間操作 一定の文字出現する最大の単調増加文字列), 我々は、より多くの情報をここで見つけました https://qiita.com/recuraki/items/654bcc8eff91c95b54f0著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .