O(N)で567. Permutation in String

2つの文字列s1とs2が与えられ、s1の並び替えがs2に含まれるかどうか（s1の順列がs2の部分文字列か）判定する問題。

Can you solve this real interview question? Permutation in String - Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherw...

最初に思いついた解法

s1, s2 の長さをn1, n2とする。

s2から長さn1の文字列を切り出し、collections.Counterで得られる各文字の出現回数がs1と一致すればOK。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        n1 = len(s1)
        n2 = len(s2)
        
        if n2 < n1:
            return False

        s1c = Counter(s1)
        
        for i in range(n2 - n1 + 1):
            temp = s2[i:i+n1]
            s2c = Counter(temp)
            if s1c == s2c:
                return True
        
        return False

一見ループ1回でO(N)の解法に見えるが、Counterの内部はどうなっているのか。

Build software better, together

GitHub is where people build software. More than 100 million people use GitHub to discover, fork, and contribute to over 330 million projects.

def _count_elements(mapping, iterable):
    'Tally elements from the iterable.'
    mapping_get = mapping.get
    for elem in iterable:
        mapping[elem] = mapping_get(elem, 0) + 1

文字列を1個ずつ数えており、Counterは辞書を構築するためにO(N)の時間を必要とする。

そのため上記の回答はO(N^2)になってしまう。

これを高速化するために、sliding windowsの考えを適応した。

すなわち、s2から長さn1の文字列でCounterを構築し、1文字ずつずらしながらCounterを足し引きしていく。

今回はCounterのソースコードを参考に、辞書の構築も自前で実装してみた。

class Solution:
    def freqs(self, s):
        f = {}
        for i in s:
            f.setdefault(i, 0)
            f[i] += 1
        
        return f
        
        
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1 = len(s1)
        n2 = len(s2)
        
        if n1 > n2:
            return False
        
        f1 = self.freqs(s1)
        f2 = self.freqs(s2[:n1])
        
        if f1 == f2:
            return True

        for i in range(n2 - n1):
            left = s2[i]
            right = s2[i+n1]
            
            if f2[left] == 1:
                del f2[left]
            else:
                f2[left] -= 1
            
            f2.setdefault(s2[i+n1], 0)
            f2[s2[i+n1]] += 1
            
            if f1 == f2:
                return True
        
        return False

含まれる文字のカウント freqs でO(N)

ループがO(N)、値の足し引きはO(１）

トータルでO(N+N)=O(N)で解くことが出来るようになった。

参考