😊

【LeetCode】763. Partition Labelsを解く

2021/05/04に公開

問題概要

小文字のアルファベットからなる文字列sが与えられる．このとき，「各文字がただ一つの部分文字列に含まれる」という条件を満たすように，出来るだけ多くの部分文字列に分割することを考える．
上記の条件を満たす，各部分文字列のサイズからなるリストを返せ．

例：

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
ababcbaca | defegde | hijhklij
のように分割する．

制約

$1 \leq S.length \leq 500$
Sは，a-zの小文字のアルファベットからなる

考えたこと

入力sをleft = 0から順にみていき，

現在見ているアルファベットs[left]が最後に出現するインデクスrightを保持
rightまでに含まれるアルファベットについて，そのアルファベットが最後に出現するインデクスの内最大の値であるnextを保持
1. $right < next$ のとき：right = nextに更新し，新しいrightについて②の操作を行う
2. rightと現在見ているアルファベットのインデクスが等しいとき：
  resにright - left + 1を追加
  left = right + 1に更新
rightが最後のインデクスになるまで①-③を繰り返す

という手順で処理すればよさそう．

以下，例題を用いて実際の動きを見てみる：
ステップ1：
先頭のアルファベットaが最後に現れるのは9番目である．

a b a b c b a c a d e f e g d e h i j h k l i j 
↑               ↑
left           right

s[left:right+1]に含まれるb,cは全てこの部分文字列に含まれているため，rightの更新は行われない．従って，一つ目の部分文字列はs[0:9] = 'ababcbaca'となる．

ステップ2：
一つ目の分割点が分かっているため，left = right + 1に更新する．
s[left] = 'd'が最後に現れるのは14番目である．

a b a b c b a c a | d e f e g d e h i j h k l i j 
               　   ↑         ↑
                  left       right

ただし，s[left:right+1]に含まれる'e'が最後に現れるのは15番目でrightより大きい値であるため，right = 15に更新する．

a b a b c b a c a | d e f e g d e h i j h k l i j 
               　   ↑           ↑
                  left        right

s[left:right]に含まれるd，e，f，gは全てこの部分文字列に含まれているため，rightの更新は行われない．従って，二つ目の部分文字列はs[9:16] = 'defegde'となる．

ステップ3：
まず，left = right + 1に更新する．
s[left] = 'h'が最後に現れるのは19番目である．

a b a b c b a c a | d e f e g d e | h i j h k l i j 
               　                   ↑      ↑
                                  left    right

ただし，s[left:right]に含まれるi，jはright以降にも存在する．
iが最後に現れるのは22番目でrightより大きいため，right = 22に更新する．

a b a b c b a c a | d e f e g d e | h i j h k l i j 
               　                   ↑           ↑
                                  left       right

s[left:right]に含まれるjはright以降にも存在する．
jが最後に現れるのは23番目でrightより大きいため，right = 23に更新する．

a b a b c b a c a | d e f e g d e | h i j h k l i j 
               　                   ↑             ↑
                                  left          right

これはsの最後の文字であるためこれ以上rightの更新は発生しない．

以上より，例題は以下のように分割することができる．

a b a b c b a c a | d e f e g d e | h i j h k l i j |

実際のコードは以下のようになる：

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        last = {c: i for i, c in enumerate(S)} # 各アルファベットが最後に現れるインデクス
        res = []
        left, right = 0, 0
        for i, c in enumerate(S):
            right = max(right, last[c])
            if i == right:
                res.append(right - left + 1)
                left = right + 1
        
        return res

上記プログラムでは，各アルファベットが最後に現れるインデクスをあらかじめlastとして算出することで計算回数を減らすように工夫している．

問題概要

制約

考えたこと

Discussion