King Of Interviews

Permutation in String: 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.

Try this Problem on your own or check similar problems:

Solution:

class Solution {
  public boolean checkInclusion(String s1, String s2) {
      int[] freqMap = new int[26];
      int l1 = s1.length(), l2 = s2.length();

      if(l1 > l2) return false;

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

      if(found(freqMap)) return true;

      for(int i = l1; i < l2; ++i){
          freqMap[s2.charAt(i) - 'a']--;
          freqMap[s2.charAt(i-l1) - 'a']++;
          if(found(freqMap)) return true;
      }

      return false;
  }

  private boolean found(int[] arr){
      for(int i: arr){
          if(i != 0) return false;
      }
      return true;
  }
}

Time/Space Complexity:

Time Complexity: O(l2) where l2 is the length of longer string
Space Complexity: O(1)

Explanation:

We iterate over the shorter string (the one that we’re trying to find permutation for in the longer string), and for each character we increment the occurrence if it’s present in the shorter string or decrement if it’s present in the longer one. In other words, we’re keeping a window size of length l1 (length of the shorter string). If we find a permutation all element’s frequencies should be 0 since we decrement and increment the same number of times. We iterate over the longer string while keeping the window size of l1, each time decrementing the number of occurrences for the character that’s currently the start of our window i-l1 since we’re throwing it away and shifting the window to the right and incrementing the character we found after we shifted one character to right (our new end of the window). Each time we check if we have the same number of characters in the window of the longer string and the whole shorter one. We use s1.charAt(i) - 'a' to map lowercase letters to range 0..25 (since by the problem statement we only have lowercase letters in both of the input strings).

Permutation in String