438.find-all-anagrams-in-a-string.md

438. Find All Anagrams in a String

Clarification Questions

• Is the length of p <= the length of s?
• Is p or s empty?

Test Cases

Normal Cases

Input: s = "abab", p = "ab"
Output: [0,1,2]

Input: s = "abcabdbac", p = "abc"
Output: [0,1,2,6]

Edge / Corner Cases

• The length of p is greater than the length of s.

Breakdowns

1. Given two strings, how to determine if the two strings are anagrams?

Count the frequency of each character in the two strings, then compare.

2. How to iterate all possible substrings of size p in s?

• For loop from 0 to s.length - p.length and inner loop from 0 to p.length.
• Sliding window of size p.

Sliding Window

s = [X X X X X X X ...]
p =      |-----|

We can maintain a window of size p and see if the occurrence of each character in the window is the same as substring of s. Then we slide this window to check every possible substring of s.

// Fixed size sliding window
fun findAnagrams(s: String, p: String): List<Int> {
    val countP = IntArray(26)
    for (c in p) {
        countP[c - 'a']++
    }
    var left = 0
    var right = 0
    val countS = IntArray(26)
    val results = mutableListOf<Int>()
    val k = p.length
    for (right in 0 until s.length) {
        countS[s[right] - 'a']++
        // Remember to check if the window size is greater than k: right >= k
        if (right >= k) countS[s[right - k] - 'a']--

        // Here we don't have to check if the window size is equal to k, 
        // countS == countP implies that the window size is equal to k.
        if (countS.contentEquals(countP)) {
            results.add(right - k + 1)
        }
    }
    return results
}

// General sliding window template
fun findAnagrams(s: String, p: String): List<Int> {
    val countP = IntArray(26)
    for (c in p) {
        countP[c - 'a']++
    }
    var left = 0
    val countS = IntArray(26)
    val results = mutableListOf<Int>()
    for (right in 0 until s.length) {
        countS[s[right] - 'a']++
        while (right - left + 1 > p.length) {
            countS[s[left] - 'a']--
            left++
        }
        if (countS.contentEquals(countP)) {
            results.add(left)
        }
    }
    return results
}

• Time Complexity: O(P + (S - P) * C), where P, S and C represent the length of p, s and how many different characters in the two strings.
• Space Complexity: O(1).

Hash Table

Not optimized. TC: O(S * P), SC: O(S + P).

fun findAnagrams(s: String, p: String): List<Int> {
    val results = mutableListOf<Int>()
    val len = p.length
    val fingerprintP = fingerprint(p)
    for (i in 0..(s.length - len)) {
        val fingerprintS = fingerprint(s.slice(i until i + len))
        if (fingerprintS == fingerprintP) {
            results.add(i)
        }
    }
    return results
}

private fun fingerprint(str: String): String {
    val fingerprint = StringBuilder()
    val frequencyMap = IntArray(26)
    for (c in str) {
        frequencyMap[c - 'a']++
    }
    for (i in 0 until 26) {
        if (frequencyMap[i] > 0) {
            fingerprint.append("${'a' + i}${frequencyMap[i]}")                
        }
    }
    return fingerprint.toString()
}