Problem

Given two strings s1 and s2, determine if s1 contains any substring that is an anagram of s2. An anagram is a rearrangement of all the letters of a string. Return true if such a substring exists, otherwise return false.

Examples

Example 1

1
2
3

Input:  s1 = "coding interview questions", s2 = "weivretni"
Output: true
Explanation: "interview" is a substring of s1 and is an anagram of s2.

Example 2

1
2
3

Input:  s1 = "coding interview questions", s2 = "abcde"
Output: false
Explanation: No substring of s1 is an anagram of s2.

Solution

We have a similar problem - Find anagrams of a string in another string. But there we have find the anagram, here we have to just check.

In case you don’t know what anagram is – check it out here - Anagram Definition.

Method 1 - Using Sliding window

Solution

Method 1 - Brute force

A basic brute force method is to generate all possible substrings of s1 with the same length as s2 and check each one for being an anagram. One way to verify an anagram is by computing a hash for each string, such as assigning a unique prime number to each character and multiplying these primes for the hash; this allows linear-time comparison. However, since there are O(N^2) substrings and each check takes O(M), the overall time complexity is O(N^2 * M), which is inefficient and generally not recommended.

Method 2 - Sliding window

  • An anagram of s2 must have the same character counts as s2.
  • We can use a sliding window of length equal to s2 over s1 and compare character counts.
  • If any window matches, return true.

Approach

  1. If len(s2) > len(s1), return false.
  2. Count the frequency of each character in s2.
  3. Use a sliding window of size len(s2) over s1:
    • Maintain a count of characters in the current window.
    • If the counts match at any point, return true.
  4. If no window matches, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public boolean containsAnagram(String s1, String s2) {
        if (s2.length() > s1.length()) return false;
        int[] cntS2 = new int[256], cntW = new int[256];
        for (char c : s2.toCharArray()) cntS2[c]++;
        for (int i = 0; i < s2.length(); i++) cntW[s1.charAt(i)]++;
        if (matches(cntS2, cntW)) return true;
        for (int i = s2.length(); i < s1.length(); i++) {
            cntW[s1.charAt(i)]++;
            cntW[s1.charAt(i - s2.length())]--;
            if (matches(cntS2, cntW)) return true;
        }
        return false;
    }
    private boolean matches(int[] a, int[] b) {
        for (int i = 0; i < 256; i++) if (a[i] != b[i]) return false;
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def contains_anagram(self, s1: str, s2: str) -> bool:
        if len(s2) > len(s1):
            return False
        from collections import Counter
        cnt_s2: Dict[str, int] = Counter(s2)
        cnt_w: Dict[str, int] = Counter(s1[:len(s2)])
        if cnt_s2 == cnt_w:
            return True
        for i in range(len(s2), len(s1)):
            cnt_w[s1[i]] += 1
            cnt_w[s1[i - len(s2)]] -= 1
            if cnt_w[s1[i - len(s2)]] == 0:
                del cnt_w[s1[i - len(s2)]]
            if cnt_s2 == cnt_w:
                return True
        return False

Complexity

  • ⏰ Time complexity: O(N) where N is the length of string s1.
  • 🧺 Space complexity: O(1) (since the alphabet size is constant, e.g., 26 or 256).