尺取り法による部分文字列の探索

概要

ある条件を満たす部分文字列を探索する場合、総当たりで探索を行うと計算量がO(n^2)になり、制限時間に間に合わない場合がほとんどです。そこで今回は、尺取り法（しゃくとり法）によって効率的に部分文字列を探索する手法を紹介します。

例題

ABC032 C - 列

概要

長さ $n$ の0を含む自然数からなる数列 $a_1, a_2, \dots, a_n$ と自然数 $K$ が与えられる。数列の連続する部分列で、その積が $K$ 以下となるもののうち、最大の長さを求めよ (条件を満たす区間がないときは $0$ を出力)。

例

　条件: $n = 7$, $K = 6$, $a = (4, 3, 1, 1, 2, 10, 2)$
　解答: $4$

条件を満たす最長の部分列は(3, 1, 1, 2) であり、その長さは4である

実装例

import sys
n, k = map(int, input().split())
s = []
ans = 0

for i in range(n):
    s.append(int(input()))

# 0が一つでも含まれている場合、積は0になり必ず条件を満たすため、数列の長さをそのまま返す
if any(n == 0 for n in s):
    print(n)
    sys.exit()

# 全ての要素がKを超えている場合、条件を満たす部分列は存在しない
if all(n > k for n in s):
    print(0)
    sys.exit()

# 右端のindex
r = 0
# 第1項を積として持っておく
temp = s[0]

for l in range(n-1):
    if l > 0:
        temp //= s[l-1]

    while r <= n - 1:
        # 積がK以下の場合、部分列の長さを調べて最長なら更新する
        if temp <= k:
            ans = max(ans, r - l + 1)
            r += 1
            if r <= n - 1:
                temp *= s[r]
        else:
            break

print(ans)

ABC124 D - Handstand

概要

0と1 からなる長さ N の文字列 S と正整数 K が与えられる。連続する0の列をK回まで1の列に変換できる時、連続する1の列を最長でどれだけの長さにできるかを求めよ

方針

連続する0の列をK個以下含むような最長の部分列の長さを求めれば良い

実装例

n, k = map(int, input().split())
s = input()
ans = 0

# 連続する0の列が現れる回数を数える
cnt = 0

# lを左端、rを右端とする
r = 1
for l in range(0, n):
    if l == 0 and s[l] == '0':
        cnt += 1

    # 左端が0から1に変わるタイミングで、カウントを１減らす
    if l > 0 and s[l] == '1' and s[l-1] == '0':
        cnt -= 1

    while r <= n - 1:
        # 右端が1から0に変わるタイミング
        if s[r] == '0' and s[r-1] == '1':
            # カウントがK未満の場合は、単にカウントを増やす
            if cnt < k:
                cnt += 1
            # カウントがKに達している場合、while文を抜ける(左端:lを一つ進める）
            else:
                break
        r += 1

    # 最長部分列の長さを更新
    ans = max(ans, r - l)

print(ans)

問

文字列Sの部分文字列のうち、下記の条件を満たす最長の部分文字列Tの長さを求めよ

• TはSに含まれる連続する部分文字列である
• Tは３種類以上の文字を含んではならない

例１

入力

"eceba"

出力

3

"ece"が条件を満たす最長の部分文字列となる

例２

入力

"ccaabbb"

出力

5

"aabbb"が条件を満たす最長の部分文字列となる

実装例

条件を満たす最長の部分文字列の長さを求める

    # 条件判定のメソッドを用意しておく
    def isValid(t):
        charSet = set()
        for c in t:
            charSet.add(c)
            # 3種類以上の文字を含む場合はアウト
            if len(charSet) > 2:
                return False
        return True

    def longestSubstringLength(s):
        maxLen = 0

        for i in range(len(s)):
            l = i
            r = i + 1

            while l < r and r < len(s):
                # lからrの範囲の部分文字列を調べる
                temp = s[l:r+1]

                # 条件を満たす部分文字列が見つかったら、rを右にずらして探索範囲を広げる
                if isValid(temp):
                    if len(temp) > maxLen:
                        maxLen = len(temp)
                    r += 1
                # 部分文字列が条件を満たさない（3種類以上の文字を含む）場合、whileループから抜ける
                else:
                    break

        return maxLen

参考

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ