LeetCode Entry

567. Permutation in String

4.02.2023 medium 2023 kotlin

to decrease cost of comparing arrays, we can also use hashing

567. Permutation in String medium

blog post

    fun checkInclusion(s1: String, s2: String): Boolean {
        val freq1 = IntArray(26) { 0 }
        s1.forEach {  freq1[it.toInt() - 'a'.toInt()]++  }
        val freq2 = IntArray(26) { 0 }
        for (i in 0..s2.lastIndex) {
            freq2[s2[i].toInt() - 'a'.toInt()]++
            if (i >= s1.length) freq2[s2[i - s1.length].toInt() - 'a'.toInt()]--
            if (Arrays.equals(freq1, freq2)) return true
        }
        return false
    }

Telegram

https://t.me/leetcode_daily_unstoppable/108

Intuition

We can count the chars frequencies in the s1 string and use the sliding window technique to count and compare char frequencies in the s2.

Approach

• to decrease cost of comparing arrays, we can also use hashing

  Complexity

• Time complexity: \(O(n)\)
• Space complexity: \(O(1)\)