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.

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba"). Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Constraints:

Contents

In this approach, we are going to apply sliding window technique, using two pointers left and right, and using either a HashMap or an array to store character counts in both strings, and check whether the characters count from s1 matched with characters count in s2's current window.

Implementation steps:
Check both implementations using HashMap and using an array with fixed size (26). Implementation using two HashMaps: import java.util.HashMap; public class PermutationInString { static boolean checkInclusion(String s1, String s2) { if(s2.length() < s1.length()) { return false; } // Two maps, one stores the character count of S1 // Other map stores the characters in current window HashMap<Character, Integer> s1_count = new HashMap<>(); for(char c: s1.toCharArray()) { s1_count.merge(c, 1, Integer::sum); } int left =0; int right=0; HashMap<Character, Integer> s2_count = new HashMap<>(); while(right < s2.length()) { s2_count.merge(s2.charAt(right), 1, Integer::sum); /* When s2_count reaches exceeds sliding window size, then remove left most (>= because indexes starts with 0) */ if(right >= s1.length()) { int new_count = s2_count.merge(s2.charAt(left), -1, Integer::sum); if(new_count == 0){ s2_count.remove(s2.charAt(left)); } left++; } if(s1_count.equals(s2_count)) { return true; } right++; } return false; } public static void main(String[] args) { System.out.println("################ Using HashMaps #######################"); System.out.println(checkInclusion("ab","eidbaooo")); System.out.println(checkInclusion("ab","eidboaoo")); } } Implementation using temporary arrays with size 26: import java.util.Arrays; public class PermutationInString { static boolean checkInclusionUsingArrays(String s1, String s2) { if(s2.length() < s1.length()) { return false; } int[] s1_count = new int[26]; int[] s2_count = new int[26]; for(char c: s1.toCharArray()) { s1_count[c-'a']++; } int left =0; int right=0; while(right < s2.length()) { s2_count[s2.charAt(right)-'a']++; /* When s2_count reaches exceeds sliding window size, then remove left most (>= because indexes starts with 0) */ if(right >= s1.length()) { s2_count[s2.charAt(left)-'a']--; left++; } if(Arrays.equals(s1_count, s2_count)) { return true; } right++; } return false; } public static void main(String[] args) { System.out.println("################ Using temp arrays with length 26 #######################"); System.out.println(checkInclusionUsingArrays("ab","eidbaooo")); System.out.println(checkInclusionUsingArrays("ab","eidboaoo")); } }
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s2.
Space complexity: O(1), since the input can contain only lowercase English letters, so the HashMap or array is going to contain at most 26 entries.

In terms of time complexity of this solution, it is going to be same as above, but we can reduce the constant factor, previous solution time complexity is O (26 * n) since we are checking character count at every character of s2, in this approach we are going to reduce the constant factor of 26.

The main intution of this solution is, say if the input strings are "abc" and "abxyzabc", similar to above implementation we will be storing character count of s1 into an array. Then, when storing characters count from s2 within the window size of s1's length, we would be adjusting character count, during this check we will maintain another variable matches that keeps track of 26 characters count, and there will be a window where the matches count will be equal to 26, that means characters count in s1 matches with the characters count from the window of s2.

Let's understand this step by step.

public class PermutationInString { static boolean checkInclusionUsingArraysAndMatchCount(String s1, String s2) { if(s1.length() > s2.length()) { return false; } int[] s1_count = new int[26]; int[] s2_count = new int[26]; for(int i=0; i<s1.length(); i++) { s1_count[s1.charAt(i) -'a']++; s2_count[s2.charAt(i) -'a']++; } int matches = 0; for(int i=0; i<s1_count.length; i++) { matches += (s1_count[i] == s2_count[i]) ? 1 : 0; } int left = 0; // read from where we left off above for(int i=s1.length(); i<s2.length(); i++) { if(matches == 26) { return true; // means all characters count matched } int rightCharIndex = s2.charAt(i) -'a'; s2_count[rightCharIndex]++; // after adding the next character, check if count at the index between s1_count and s2_count changed ? if(s1_count[rightCharIndex] == s2_count[rightCharIndex]) { matches++; } else if(s1_count[rightCharIndex] +1 == s2_count[rightCharIndex]) { matches--; } // since we have added right element, remove the left element from count and re-check int leftCharIndex = s2.charAt(left) - 'a'; s2_count[leftCharIndex]--; if(s1_count[leftCharIndex] == s2_count[leftCharIndex]) { matches++; } else if(s1_count[leftCharIndex] - 1 == s2_count[leftCharIndex]) { matches--; } left++; } return matches == 26; // in case, the match happened at the last character. } public static void main(String[] args) { System.out.println("################ Using temp arrays with length 26 and matchCount as we loop through characters #######################"); System.out.println(checkInclusionUsingArraysAndMatchCount("ab","eidbaooo")); System.out.println(checkInclusionUsingArraysAndMatchCount("ab","eidboaoo")); } }
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s2.
Space complexity: O(1), since the temporary arrays size is 26.

Above implementations source code can be found at GitHub link for Java code