Microsoft

2020-05-18

## 567. Permutation in String

### 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;

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;

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;
}
}
``````