Permutation in String

Why it belongs on this sheet

This is a solid fixed-size sliding-window problem and a good follow-up after frequency-map basics.

Pattern

Fixed-size frequency window

Approach

Maintain frequency arrays for the target string and the current window. Slide a window of the same length across the second string and compare the two arrays.

Java solution

import java.util.Arrays;

class Solution {
  public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
      return false;
    }

    int[] need = new int[26];
    int[] window = new int[26];

    for (int i = 0; i < s1.length(); i++) {
      need[s1.charAt(i) - 'a']++;
      window[s2.charAt(i) - 'a']++;
    }

    if (Arrays.equals(need, window)) {
      return true;
    }

    for (int right = s1.length(); right < s2.length(); right++) {
      window[s2.charAt(right) - 'a']++;
      window[s2.charAt(right - s1.length()) - 'a']--;

      if (Arrays.equals(need, window)) {
        return true;
      }
    }

    return false;
  }
}

Complexity

• Time: O(26 * n), which is effectively O(n)
• Space: O(1)

Interview note

For lowercase letters, arrays are cleaner and faster than maps.