Find permutation of one string into other string program

Question

Trying to make an program where it just check, if permutation of string s1 exists in string s2 or not.

Created below program and it works for below test case.

Input:

s1 = "ab"
s2 = "eidballl"

Output:

True

Explanation: s2 contains one permutation of s1 (that is ba).

But this get fail when, input s2="sdfdadddbd" , s1="ab", expected as, false, but got true.

I'm trying to figure out what is missing here. Using a sliding window approach. Below my code in c#:

   public bool CheckInclusion(string s1, string s2) {

        var intCharArray = new int[256];

        foreach(char c in s1)
        {
            intCharArray[c]++;
        }

        int start=0,end=0;
        int count=s1.Length;
        bool found=false;
        while(end<s2.Length)
        {
            if (intCharArray[s2[end]]>0) { count--;}
            intCharArray[s2[end]]--;


                Console.WriteLine("end:" + end + " start:"+ start);
                if(end-start==s1.Length) {

                    if (count==0) {return true;}
                    if (intCharArray[s2[start]]>=0)
                    {
                        count++;
                    }
                    intCharArray[s2[start]]++;
                    start++;
                }
                    end++;
            }
        return false;
        }

Answer 1

I guess the question is similar to LeetCode 567. These are simple, efficient, low-complexity accepted solutions:

C#

class Solution {
    public bool CheckInclusion(string s1, string s2) {
        int lengthS1 = s1.Length;
        int lengthS2 = s2.Length;

        if (lengthS1 > lengthS2)
            return false;

        int[] countmap = new int[26];

        for (int i = 0; i < lengthS1; i++)
            countmap[s1[i] - 97]++;


        int[] bCount = new int[26];

        for (int i = 0; i < lengthS2; i++) {
            bCount[s2[i] - 97]++;

            if (i >= (lengthS1 - 1)) {
                if (allZero(countmap, bCount))
                    return true;

                bCount[s2[i - (lengthS1 - 1)] - 97]--;
            }
        }

        return false;
    }

    private bool allZero(int[] s1, int[] s2) {
        for (int i = 0; i < 26; i++) {
            if (s1[i] != s2[i])
                return false;
        }

        return true;
    }
}

Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int lengthS1 = s1.length();
        int lengthS2 = s2.length();

        if (lengthS1 > lengthS2)
            return false;

        int[] countmap = new int[26];

        for (int i = 0; i < lengthS1; i++) {
            countmap[s1.charAt(i) - 97]++;
            countmap[s2.charAt(i) - 97]--;
        }

        if (allZero(countmap))
            return true;

        for (int i = lengthS1; i < lengthS2; i++) {
            countmap[s2.charAt(i) - 97]--;
            countmap[s2.charAt(i - lengthS1) - 97]++;

            if (allZero(countmap))
                return true;
        }

        return false;
    }

    private boolean allZero(int[] count) {
        for (int i = 0; i < 26; i++)
            if (count[i] != 0)
                return false;

        return true;
    }
}

Python

class Solution:
    def checkInclusion(self, s1, s2):
        count_map_s1 = collections.Counter(s1)
        count_map_s2 = collections.Counter(s2[:len(s1)])

        for i in range(len(s1), len(s2)):
            if count_map_s1 == count_map_s2:
                return True

            count_map_s2[s2[i]] += 1
            count_map_s2[s2[i - len(s1)]] -= 1
            if count_map_s2[s2[i - len(s1)]] == 0:
                del(count_map_s2[s2[i - len(s1)]])

        return count_map_s2 == count_map_a

Reference

The codes are explained in the following links:

• LeetCode 567 Solution

• LeetCode 567 Discussion Board

---

These two answers are also useful to look into:

• Link 1
• Link 2