Given a string str of length N and an integer K, the task is to check if a string has two non-overlapping substrings of length K as anagrams.
Examples:
Input: str = “ginfing”, K = 3
Output: Yes
Explanation:
“gin” and “ing” are the two non overlapping substrings of length 3 which are anagrams.
Therefore, the output is Yes.Input: str = “ginig”, K = 3
Output: No
Explanation:
In the given string, there are no two non overlapping substrings of length 3 which are anagrams. Note that substring “gin” and substring “nig” are anagrams, but they are overlapping, hence are not considered.
Hence, the output is No.
Approach: The idea to solve this problem is to traverse the given string and use a set to store the substrings of length K and search for two non-overlapping substrings present in the given string. Follow the steps below:
- Initialize an unordered_set set to store substrings of length K.
- Iterate over characters of the given string str using a variable i.
- If there exists a string of length K starting at index (i – 1) in str, then erase the sorted string of length K from the Set.
- If there exists a string of length K ending at index (i – 1) in str, then insert the sorted string of length K into the Set.
- If the sorted substring of length K starting at index i is found in the set, then there exist two non-overlapping substrings of length K as anagrams in str. Therefore, print “Yes” and break out of the loop. Otherwise, insert the sorted substring of length K starting at index i into the Set.
- If no pair of substrings were found after iterating through the whole string, then print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#include <iostream>using namespace std;// Function to check whether the string// s has two non-overlapping substrings// of length K as anagramsvoid anagramPairs(string str, int K){ // Stores the substrings of length K unordered_set<string> set; int l = str.length(); // Iterate through every character for (int i = 0; i < l; i++) { // If there is a substring starting // at index i - 1 of length K then // erase that substring from set if (i > 0 && K - (i - 1) - 1 < l) { string s1 = str.substr(i - 1, K); // Sort the substring sort(s1.begin(), s1.end()); // Remove from set set.erase(s1); } // If there is a substring of length // K ending at index i - 1 if ((i - 1) - K + 1 >= 0) { string s1 = str.substr( (i - 1) - K + 1, K); // Sort the substring sort(s1.begin(), s1.end()); // Insert substring into the Set set.insert(s1); } // If there is a substring of length // K starting from the i-th index if (K + i - 1 < l) { // Check if the sorted // substring is present in // the set or not string s1 = str.substr(i, K); sort(s1.begin(), s1.end()); // If present in the Set if (set.count(s1)) { cout << "Yes"; return; } // Insert the sorted // substring into the set set.insert(s1); } } // If not present in the Set cout << "No";}// Driver Codeint main(){ string str = "ginfing"; int K = 3; // Function Call anagramPairs(str, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check whether the String// s has two non-overlapping subStrings// of length K as anagramsstatic void anagramPairs(String str, int K){ // Stores the subStrings of length K HashSet<String> set = new HashSet<String>(); int l = str.length(); // Iterate through every character for (int i = 0; i < l; i++) { // If there is a subString starting // at index i - 1 of length K then // erase that subString from set if (i > 0 && K - (i - 1) - 1 < l) { String s1 = str.substring(i - 1, K); // Sort the subString s1 = sortString(s1); // Remove from set set.remove(s1); } // If there is a subString of length // K ending at index i - 1 if ((i - 1) - K + 1 >= 0) { String s1 = str.substring( (i - 1) - K + 1, K); // Sort the subString s1 = sortString(s1); // Insert subString into the Set set.add(s1); } // If there is a subString of length // K starting from the i-th index if (K + i - 1 < l) { // Check if the sorted // subString is present in // the set or not String s1 = str.substring(i, i+K); s1 = sortString(s1); // If present in the Set if (set.contains(s1)) { System.out.print("Yes"); return; } // Insert the sorted // subString into the set set.add(s1); } } // If not present in the Set System.out.print("No");}static String sortString(String inputString) { // convert input string to char array char tempArray[] = inputString.toCharArray(); // sort tempArray Arrays.sort(tempArray); // return new sorted string return new String(tempArray); } // Driver Codepublic static void main(String[] args){ String str = "ginfing"; int K = 3; // Function Call anagramPairs(str, K);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function to check whether the string# s has two non-overlapping substrings# of length K as anagramsdef anagramPairs(str, K): # Stores the substrings of length K sett = {} l = len(str) # Iterate through every character for i in range(l): # If there is a substring starting # at index i - 1 of length K then # erase that substring from sett if (i > 0 and K - (i - 1) - 1 < l): s1 = str[i - 1:i + K - 1] # Sort the substring s1 = sorted(s1) # Remove from sett del sett["".join(s1)] # If there is a substring of length # K ending at index i - 1 if ((i - 1) - K + 1 >= 0): s1 = str[(i - 1) - K + 1:i] # Sort the substring s1 = sorted(s1) # Insert substring into the Set sett["".join(s1)] = 1 # If there is a substring of length # K starting from the i-th index if (K + i - 1 < l): # Check if the sorted # substring is present in # the sett or not s1 = str[i : i + K] s1 = sorted(s1) # If present in the Set if "".join(s1) in sett: print("Yes") return #Insert the sorted # substring into the sett sett["".join(s1)] = 1 # If not present in the Set print("No")# Driver Codeif __name__ == '__main__': str = "ginfing" K = 3 # Function Call anagramPairs(str, K)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to check whether the String// s has two non-overlapping subStrings// of length K as anagramsstatic void anagramPairs(String str, int K){ // Stores the subStrings of length K HashSet<String> set = new HashSet<String>(); int l = str.Length; // Iterate through every character for (int i = 0; i < l; i++) { // If there is a subString starting // at index i - 1 of length K then // erase that subString from set if (i > 0 && K - (i - 1) - 1 < l) { String s1 = str.Substring(i - 1, K); // Sort the subString s1 = sortString(s1); // Remove from set set.Remove(s1); } // If there is a subString of length // K ending at index i - 1 if ((i - 1) - K + 1 >= 0) { String s1 = str.Substring( (i - 1) - K + 1, K); // Sort the subString s1 = sortString(s1); // Insert subString into the Set set.Add(s1); } // If there is a subString of length // K starting from the i-th index if (K + i - 1 < l) { // Check if the sorted // subString is present in // the set or not String s1 = str.Substring(i, K); s1 = sortString(s1); // If present in the Set if (set.Contains(s1)) { Console.Write("Yes"); return; } // Insert the sorted // subString into the set set.Add(s1); } } // If not present in the Set Console.Write("No");}static String sortString(String inputString) { // convert input string to char array char []tempArray = inputString.ToCharArray(); // sort tempArray Array.Sort(tempArray); // return new sorted string return new String(tempArray); } // Driver Codepublic static void Main(String[] args){ String str = "ginfing"; int K = 3; // Function Call anagramPairs(str, K);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program for the above approach// Function to check whether the string// s has two non-overlapping substrings// of length K as anagramsfunction anagramPairs(str, K) { // Stores the substrings of length K let set = new Set(); let l = str.length; // Iterate through every character for (let i = 0; i < l; i++) { // If there is a substring starting // at index i - 1 of length K then // erase that substring from set if (i > 0 && K - (i - 1) - 1 < l) { let s1 = str.substr(i - 1, K); // Sort the substring s1 = s1.split("").sort().join("") // Remove from set set.delete(s1); } // If there is a substring of length // K ending at index i - 1 if ((i - 1) - K + 1 >= 0) { let s1 = str.substr( (i - 1) - K + 1, K); // Sort the substring s1 = s1.split("").sort().join("") // Insert substring into the Set set.add(s1); } // If there is a substring of length // K starting from the i-th index if (K + i - 1 < l) { // Check if the sorted // substring is present in // the set or not let s1 = str.substr(i, K); s1 = s1.split("").sort().join("") // If present in the Set if (set.has(s1)) { document.write("Yes"); return; } // Insert the sorted // substring into the set set.add(s1); } } // If not present in the Set document.write("No");}// Driver Codelet str = "ginfing";let K = 3;// Function CallanagramPairs(str, K);</script> |
Output:
Yes
Time Complexity: O(N*(K + K*log K))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
