567.permutation-in-string.md

567. Permutation in String

Hash Table

fun checkInclusion(s1: String, s2: String): Boolean {
    val s1Count = count(s1)
    for (i in 0..s2.length - s1.length) {
        val substring = s2.substring(i until i + s1.length)
        val countSubstring = count(substring)
        var isPermutation = true
        for (i in 0 until 26) {
            if (s1Count[i] != countSubstring[i]) {
                isPermutation = false
                break
            }
        }
        if (isPermutation) return true
    }
    return false
}

private fun count(s: String): IntArray {
    val count = IntArray(26)
    for (c in s) {
        count[c - 'a']++
    }
    return count
}

Sliding Window

fun checkInclusion(s1: String, s2: String): Boolean {
    var start = 0
    var end = 0
    val s1Count = IntArray(26)
    for (s in s1) {
        s1Count[s - 'a']++
    }
    
    val s2Count = IntArray(26)
    while (end < s2.length) {
        s2Count[s2[end] - 'a']++
        while (end - start + 1 > s1.length) {
            s2Count[s2[start] - 'a']--
            start++
        }
        
        if (end - start + 1 == s1.length) {
            if (s1Count.contentEquals(s2Count)) return true
        }
        end++
    }
    return false
}

• Time Complexity: O(m + n) where m and n represents the length of two strings.
• Space Complexity: O(1).

More approaches, please see solution.