MAY-18 2020 Challenge

MAY-18 2020 Challenge : Permutation in String

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:

- The input strings only contain lower case letters.

- The length of both given strings is

in range [1, 10,000].

Solution in C++: 

class Solution {

    public boolean checkInclusion(String s1, String s2) {

        int[] map = new int[128];

        for (char c : s1.toCharArray()) {

            map[c]++;

        }

        int count = s1.length();

        char[] chars = s2.toCharArray();

        int left = 0, right = 0;

        while (right < chars.length) {

            if (map[chars[right++]]-- > 0) count--;

            while (count == 0) {

                if (right - left == s1.length()) return true;

                if (++map[chars[left++]] > 0) count++;

            }

        }

        return false;

    }

}