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

private static bool CheckPermutationInclusion(string s1, string s2)
{
    return Enumerable.Range(0, s2.Length - s1.Length)
                     .Select(i => s2.Substring(i, s1.Length))
                     .Any(x => x.All(y => s1.Contains(y)));
}

Description:

• Enumerable.Range(Int32, Int32) Method: Generates a sequence of integral numbers within a specified range.
• Enumerable.Select Method: Projects each element of a sequence into a new form.
• Enumerable.All Method: Determines whether all elements of a sequence satisfy a condition.
• Enumerable.Any Method: Determines whether any element of a sequence exists or satisfies a condition.

Do not forget using System.Linq;.

Answer 2

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

Answer 3

you need to check all characters of permutation exist in any range of [i, i + p.Length) of the string

static class StringExtensions
{
    public static bool ContainsAnyPermutationOf(this string str, string p)
    {
        Dictionary<char, int> chars_count = p.CreateChar_CountDictionary();

        for (int i = 0; i <= str.Length - p.Length; i++)
        {
            string subString = str.Substring(i, p.Length);
            if (DictionaryMatch(chars_count, subString.CreateChar_CountDictionary()))
            {
                return true;
            }
        }
        return false;
    }

    private static bool DictionaryMatch(Dictionary<char, int> dictionary1, Dictionary<char, int> dictionary2)
    {
        if (dictionary1.Count != dictionary2.Count)
        {
            return false;
        }
        foreach (var kvp in dictionary1)
        {
            if (!dictionary2.ContainsKey(kvp.Key))
            {
                return false;
            }
            dictionary2[kvp.Key] = dictionary2[kvp.Key] - 1;
            if (dictionary2[kvp.Key] == 0)
            {
                dictionary2.Remove(kvp.Key);
            }
        }
        return true;
    }

    private static Dictionary<char, int> CreateChar_CountDictionary(this string str)
    {
        Dictionary<char, int> dic = new Dictionary<char, int>();
        for (int i = 0; i < str.Length; i++)
        {
            if (!dic.ContainsKey(str[i]))
            {
                dic.Add(str[i], default);
            }
            dic[str[i]] = dic[str[i]] + 1;
        }
        return dic;
    }
}

usage:

static void Main(string[] args)
    {
        Console.WriteLine("sdfdadddbd".ContainsAnyPermutationOf("ab"));
    }