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

Constraints:

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

 public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
            return false;
        int[] s1Arr = new int[26];
        int s1Length = s1.length(), s2Length = s2.length();
        for (int i = 0; i < s1Length; i++)
            s1Arr[s1.charAt(i) - 'a']++;
        for (int i = 0; i <= s2Length - s1Length; i++) {
            int[] s2Arr = new int[26];
            for (int j = 0; j < s1Length; j++) {
                s2Arr[s2.charAt(i + j) - 'a']++;
            }
            if (matches(s1Arr, s2Arr))
                return true;
        }
        return false;
    }
    public boolean matches(int[] s1Arr, int[] s2Arr) {
        for (int i = 0; i < 26; i++) {
            if (s1Arr[i] != s2Arr[i])
                return false;
        }
        return true;
    }
}


Try it on Leetcode

Here we are going to solve only using arrays. One string will be a permutation of another string only if both of them contain the same charaters with the same frequency. We can consider every possible substring in the long string $s2$ of the same length as that of $s1$ and check the frequency of occurence of the characters appearing in the two. If the frequencies of every letter match exactly, then only $s1$'s permutation can be a substring of $s2$.

1) Count all characters of s1

2) For each character of s2, if any character of s1 is found, then for length of s1, s2 array is check for match s1 array. If it's matches return true.

3) Else repeat above step till end of s2 string to find permutation of s1.

The same approach can be solved using HashMap. If so, it end up in Time Limit Exceeded.

NOTE:

This problem can be solved using Sliding Window approach similar to Find All Anagrams in a String

Also Check it out:

Click here for July month challenges with solution and explanation

Click here for June month challenges with solution and explanation

Click here for May month challenges with solution and explanation

Click here for April month challenges with solution and explanation

Click Follow button to receive updates from us instantly.

Please let us know about your views in comment section.

Help Others, Please Share..!!!!

                                                     😍..Happy Coding...😍