LeetCode 567. Permutation in String

LeetCode Notes [36]

Problem

Permutation in String - LeetCode

Approach: Sliding Window

One string will be a permutation of another string only if both of them contain the same characters with the same frequency. We can consider every possible substring in the long string s2 of the same length as that of s1 and check the frequency of occurrence of the characters appearing in the two. If the frequencies of every letter match exactly, then only s1’s permutation can be a substring of s2.

In order to implement this approach, instead of sorting and then comparing the elements for equality, we make use of a hashmap table which stores the frequency of occurence of all the characters in the short string s1. We consider every possible substring of s2 of the same length as that of s1, find its corresponding hashmap as well. Thus, the substrings considered can be viewed as a window of length as that of s1 iterating over s2. If the two hashmaps obtained are identical for any such window, we can conclude that s1’s permutation is a substring of s2, otherwise not.

Implementation

class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        val s2CharArray = s2.toCharArray()
        for (i in 0..s2.length - s1.length) {
            val table = mutableMapOf<Char, Int>()
            for (j in i until i + s1.length) {
                val char = s2CharArray[j]
                table.putIfAbsent(char, 0)
                table[char] = table[char]!! + 1
            }
            val s1CharArray = s1.toCharArray()
            for (j in s1.indices) {
                val char = s1CharArray[j]
                if (table.containsKey(char)) {
                    table[char] = table[char]!! - 1
                }
            }
            if (table.any { it.value != 0 }) continue
            else return true
        }
        return false
    }
}

Complexity Analysis

Let l​ be the max length of string s1​ and s2​.

• Time Complexity: O(l²)
• Space Complexity: O(1). Hashmap contains at most 26 key-value pairs.