Problem of The Day: Permutation in String

Problem Statement

Brute Force [TLE]

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        counter1 = Counter(s1)
        for i, c in enumerate(s2):
            if c in counter1:
                counter = Counter(s1)
                j = i
                while j < len(s2) and s2[j] in counter:
                    counter[s2[j]] -= 1
                    if counter[s2[j]] == 0:
                        del counter[s2[j]]
                    j += 1
                if len(counter) == 0:
                    return True
        return False

Solution

Aprroach using array of size 26

    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1 = len(s1)
        n2 = len(s2)

        if n1 > n2:
             return False

        s1Count, s2Count = [0] * 26, [0] * 26

        for i in range(n1):
             s1Count[ord(s1[i])- ord('a')] += 1
             s2Count[ord(s2[i])- ord('a')] += 1

        if s1Count == s2Count:
            return True

        for i in range(n1, n2):
            s2Count[ord(s2[i]) - ord('a')] += 1
            s2Count[ord(s2[i - n1]) - ord('a')] -= 1

            if s1Count == s2Count:
                return True

        return False

• time: O(len(s2))
• space: O(1)

Approach using Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        cntr, w = Counter(s1), len(s1)

        for i in range(len(s2)):
            if s2[i] in cntr:
                cntr[s2[i]] -= 1
            if i >= w and s2[i-w] in cntr:
                cntr[s2[i-w]] += 1

            if all([cntr[i] == 0 for i in cntr]): # see optimized code below
                return True

        return False

Editorial Solution

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
            return false;
        int[] s1arr = new int[26];
        int[] s2arr = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            s1arr[s1.charAt(i) - 'a']++;
            s2arr[s2.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (matches(s1arr, s2arr))
                return true;
            s2arr[s2.charAt(i + s1.length()) - 'a']++;
            s2arr[s2.charAt(i) - 'a']--;
        }
        return matches(s1arr, s2arr);
    }

    public boolean matches(int[] s1map, int[] s2arr) {
        for (int i = 0; i < 26; i++) {
            if (s1arr[i] != s2arr[i])
                return false;
        }
        return true;
    }
}