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の内部はどうなっているのか。

File not found · python/cpython

The Python programming language. Contribute to python/cpython development by creating an account on GitHub.

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)で解くことが出来るようになった。

参考

What is the time complexity of collections.Counter() in Python?

collection.Counter("bcdefffaa") returns output: Counter({'f': 3, 'a': 2, 'c': 1, 'b': 1, 'e': 1, 'd': 1}) Since the result is in descended sorted order of value...