4. Permutation in String

Description

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1’s permutations is the substring of s2.

Example 1:
Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:
Input: s1 = “ab”, s2 = “eidboaoo”
Output: false

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

Approach

• The if statement is used so that the window is always of fixed length that is by removing the frequency of first character
• Time: O(n) Space: O(26+26)

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];
 
        for (int i = 0; i < s1.length(); i++)
            freq1[s1.charAt(i) - 'a']++;
 
        for (int i = 0; i < s2.length(); i++) {
            freq2[s2.charAt(i) - 'a']++;
            if(i >= s1.length())
                freq2[s2.charAt(i - s1.length()) - 'a']--;
            if(Arrays.equals(freq1,freq2))
                return true;
        }
 
        return false;    
    }
}