Given two strings S1 and S2, the task is to check if S2 contains an anagram of S1 as its substring.
Examples:
Input: S1 = “ab”, S2 = “bbpobac” Output: Yes Explanation: String S2 contains anagram “ba” of S1 (“ba”). Input: S1 = “ab”, S2 = “cbddaoo” Output: No
Approach: Follow the steps below to solve the problem:
Below is the implementation of the above approach:
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if string s2 // contains anagram of the string // s1 as its substring bool checkAnagram(string s1, string s2) { // Stores frequencies of // characters in substrings of s2 vector s2hash(26, 0); // Stores frequencies of // characters in s1 vector s1hash(26, 0); int s1len = s1.size(); int s2len = s2.size(); // If length of s2 exceeds length of s1 if (s1len > s2len) return false; int left = 0, right = 0; // Store frequencies of characters in first // substring of length s1len in string s2 while (right < s1len) { s1hash[s1[right] - 'a'] += 1; s2hash[s2[right] - 'a'] += 1; right++; } right -= 1; // Perform Sliding Window technique while (right < s2len) { // If hashmaps are found to be // identical for any substring if (s1hash == s2hash) return true; right++; if (right != s2len) s2hash[s2[right] - 'a'] += 1; s2hash[s2[left] - 'a'] -= 1; left++; } return false; } // Driver Code int main() { string s1 = "ab"; string s2 = "bbpobac"; if (checkAnagram(s1, s2)) cout << "YES\n"; else cout << "No\n"; return 0; }
Output:
YES