Permutation in String C++ programming competition question Interview question. 

Question:

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.

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:

1 <= s1.length, s2.length <= 104

s1 and s2 consist of lowercase English letters.

 

 Answer:

Here's a solution to check if one of the permutations of s1 is a substring of s2 in C++:

Code:

class Solution {

public:

    bool checkInclusion(string s1, string s2) {

        int s1_len = s1.length();

        int s2_len = s2.length();

        if (s1_len > s2_len) {

            return false;

        }

        vector<int> s1_count(26, 0), window(26, 0);

        for (int i = 0; i < s1_len; i++) {

            s1_count[s1[i] - 'a']++;

            window[s2[i] - 'a']++;

        }

        for (int i = 0; i < s2_len - s1_len; i++) {

            if (s1_count == window) {

                return true;

            }

            window[s2[i] - 'a']--;

            window[s2[i + s1_len] - 'a']++;

        }

        return s1_count == window;

    }

};

Explanation

1. First, we check if the length of s1 is greater than the length of s2. If so, we return false as it's not possible for one of s1's permutations to be a substring of s2.
2. We create two arrays, s1_count and window, to store the frequency of each letter in s1 and s2, respectively.
3. In the first for loop, we initialize the window array with the frequency of letters in the first s1_len characters of s2.
4. In the second for loop, we slide the window along s2 and update the frequency of letters in the window.
5. If the frequency of letters in the window is the same as s1_count, we return true.
6. After the loop, we return the result of the comparison between s1_count and window.

Kindly share it with your friends if this is helpful. Thank you.