Link
Youmin's LeetCode
Search

Medium Hash Table Two Pointers

Facebook

Google

Microsoft

2020-05-18

567. Permutation in String

Similar Questions: LeetCode Question 438, LeetCode Question 1456

Question:

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

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

Note:

  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

Solution:

Similar to LeetCode Question 438, just change the return value to boolean

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] hash = new int[256];
        
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0 || s1.length() > s2.length()) return false;
        
        for(char c: s1.toCharArray()) {
            hash[c] += 1; 
        } 
        
        int targetlength = s1.length(), left = 0, right = 0, counter = s1.length();
        
        for (char c: s2.toCharArray()) {
            hash[c]--;
            if (hash[c] >= 0) {
                counter--;
            }
            if (counter == 0) {
                return true;
            }
            if (right - left == targetlength - 1) {
                if (hash[s2.charAt(left)] >= 0) {
                    counter++;
                }
                hash[s2.charAt(left)]++;
                left++;
            }
            right++;
        }
        return false;
        
    }
}

A shorter version of the solution.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
      List<Integer> list = new ArrayList<>();
      
      if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) return false;
      
      int[] hash = new int[256]; 

      for (char c : s1.toCharArray()) {
          hash[c]++;
      }
      
      int left = 0, right = 0, count = s1.length();
      while (right < s2.length()) {

          if (hash[s2.charAt(right++)]-- >= 1) count--; 
          
          if (count == 0) return true;

          if (right - left == s1.length() && hash[s2.charAt(left++)]++ >= 0) count++;
      }
      return false;
    }
}