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
Australia
UK
UAE
Singapore
Canada
New
Zealand
Malaysia
USA
India
South
Africa
Ireland
Saudi
Arab
Qatar
Kuwait
Hongkong
Copyright 2016-2023 www.programmingshark.com - All Rights Reserved.
Disclaimer : Any type of help and guidance service given by us is just for reference purpose. We never ask any of our clients to submit our solution guide as it is, anywhere.