Given a string S, the task is to check if S contains a pair of substrings of length K which are anagrams of each other and doesn’t contain the character X in them. If no such substring exists, print -1.
Examples:
Input: S = “neveropen”, X = ‘f’, K = 5
Output: neveropen neveropen
Explanation:
Substrings “neveropen” and “neveropen” are anagrams of each other and does not contain ‘f’.Input: S = “rotator”, X = ‘a’, K = 3
Output: rot tor
Explanation:
Substrings “rot” and “tor” are anagrams of each other and does not contain ‘a’.
Approach:
The idea is to generate prefix sum on the basis of characters. Follow the steps below to solve the problem:
- Iterate over the string and generate frequencies of substrings by using the prefix sum array.
- If a substring with same frequency of characters is already present in the HashMap.
- Otherwise, store the frequency of characters of the substring with the current substring in the HashMap, if the frequency of the character X in the substring is 0.
Below is the implementation of the above approach:
C++
// c++ code for the above approach#include <cstring>#include <iostream>#include <unordered_map>#define MOD 1000000007using namespace std;// Class to represent a Substring// in terms of frequency of// characters present in itclass Substring {public: int count[26]; Substring() { memset(count, 0, sizeof(count)); } bool operator==(const Substring& other) const { for (int i = 0; i < 26; i++) { if (other.count[i] != count[i]) { return false; } } return true; } size_t operator()(const Substring& s) const { size_t hash = 0; for (int i = 0; i < 26; i++) { hash += (i + 1) * s.count[i]; hash %= MOD; } return hash; }};// Function to check anagramsvoid checkForAnagrams(string s, int n, char X, int k){ bool found = false; // Prefix array to store frequencies // of characters int prefix[n + 1][26]; memset(prefix, 0, sizeof(prefix)); for (int i = 0; i < n; i++) { prefix[i][s[i] - 'a'] += 1; } // Generate prefix sum for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) { prefix[i][j] += prefix[i - 1][j]; } } // Map to store frequencies unordered_map<Substring, int, Substring> map; // Check for anagrams for (int i = 0; i < n; i++) { if (i + k > n) { break; } // Generate frequencies of characters // of substring starting from i Substring sub; for (int j = 0; j < 26; j++) { sub.count[j] = prefix[i + k - 1][j] - (i - 1 >= 0 ? prefix[i - 1][j] : 0); } // Check if forbidden character is // present, then continue if (sub.count[X - 'a'] != 0) { continue; } // If already present in HashMap if (map.count(sub) > 0) { found = true; // Print the substrings cout << s.substr(map[sub], k) << " " << s.substr(i, k) << endl; break; } else { map[sub] = i; } } // If no such substring is found if (!found) { cout << "-1" << endl; }}// Driver Codeint main(){ string s = "rotator"; int n = s.length(); char X = 'a'; int k = 3; checkForAnagrams(s, n, X, k); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;// Class to represent a Substring// in terms of frequency of// characters present in itclass Substring { int MOD = 1000000007; // Store count of characters int count[]; Substring() { count = new int[26]; } public int hashCode() { int hash = 0; for (int i = 0; i < 26; i++) { hash += (i + 1) * count[i]; hash %= MOD; } return hash; } public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Substring)) return false; Substring ob = (Substring)o; for (int i = 0; i < 26; i++) { if (ob.count[i] != count[i]) return false; } return true; }}class GFG { // Function to check anagrams static void checkForAnagrams(String s, int n, char X, int k) { boolean found = false; // Prefix array to store frequencies // of characters int prefix[][] = new int[n + 1][26]; for (int i = 0; i < n; i++) { prefix[i][s.charAt(i) - 97]++; } // Generate prefix sum for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) prefix[i][j] += prefix[i - 1][j]; } // Map to store frequencies HashMap<Substring, Integer> map = new HashMap<>(); // Check for anagrams for (int i = 0; i < n; i++) { if (i + k > n) break; // Generate frequencies of characters // of substring starting from i Substring sub = new Substring(); for (int j = 0; j < 26; j++) { sub.count[j] = prefix[i + k - 1][j] - (i - 1 >= 0 ? prefix[i - 1][j] : 0); } // Check if forbidden character is // present, then continue if (sub.count[X - 97] != 0) continue; // If already present in HashMap if (map.containsKey(sub)) { found = true; // Print the substrings System.out.println( s.substring(map.get(sub), map.get(sub) + k) + " " + s.substring(i, i + k)); break; } else { map.put(sub, i); } } // If no such substring is found if (!found) System.out.println("-1"); } // Driver Code public static void main(String[] args) { String s = "rotator"; int n = s.length(); char X = 'a'; int k = 3; checkForAnagrams(s, n, X, k); }} |
Python3
# Python Program to implement# the above approachimport sysMOD = 1000000007# Class to represent a Substring# in terms of frequency of# characters present in itclass Substring: def __init__(self): self.count = [0] * 26 def __hash__(self): hash = 0 for i in range(26): hash += (i + 1) * self.count[i] hash %= MOD return hash def __eq__(self, other): if self is other: return True if not isinstance(other, Substring): return False ob = other for i in range(26): if ob.count[i] != self.count[i]: return False return True# Function to check anagramsdef checkForAnagrams(s, n, X, k): found = False # Prefix array to store frequencies # of characters prefix = [[0 for i in range(26)] for j in range(n + 1)] for i in range(n): prefix[i][ord(s[i]) - 97] += 1 # Generate prefix sum for i in range(1, n): for j in range(26): prefix[i][j] += prefix[i - 1][j] # Map to store frequencies map = {} # Check for anagrams for i in range(n): if i + k > n: break # Generate frequencies of characters # of substring starting from i sub = Substring() for j in range(26): sub.count[j] = prefix[i + k - 1][j] - (prefix[i - 1][j] if i - 1 >= 0 else 0) # Check if forbidden character is # present, then continue if sub.count[ord(X) - 97] != 0: continue # If already present in HashMap if sub in map: found = True # Print the substrings print(s[map[sub]:map[sub] + k], s[i:i + k]) break else: map[sub] = i # If no such substring is found if not found: print("-1")# Driver Codeif __name__ == "__main__": s = "rotator" n = len(s) X = 'a' k = 3 checkForAnagrams(s, n, X, k)# Contributed by adityasha4x71 |
C#
// c# code for the above approachusing System;using System.Collections.Generic;namespace Anagrams {// Class to represent a Substring// in terms of frequency of// characters present in itclass Substring { public int[] count; public Substring() { count = new int[26]; Array.Fill(count, 0); } public override bool Equals(object obj) { Substring other = obj as Substring; if (other == null) { return false; } for (int i = 0; i < 26; i++) { if (other.count[i] != count[i]) { return false; } } return true; } public override int GetHashCode() { const int MOD = 1000000007; int hash = 0; for (int i = 0; i < 26; i++) { hash += (i + 1) * count[i]; hash %= MOD; } return hash; }}class Program { // Function to check anagrams static void CheckForAnagrams(string s, int n, char X, int k) { bool found = false; // Prefix array to store frequencies // of characters int[, ] prefix = new int[n + 1, 26]; for (int i = 0; i < n; i++) { prefix[i, s[i] - 'a'] += 1; } // Generate prefix sum for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) { prefix[i, j] += prefix[i - 1, j]; } } // Dictionary to store frequencies Dictionary<Substring, int> map = new Dictionary<Substring, int>(); // Check for anagrams for (int i = 0; i < n; i++) { if (i + k > n) { break; } // Generate frequencies of characters // of substring starting from i Substring sub = new Substring(); for (int j = 0; j < 26; j++) { sub.count[j] = prefix[i + k - 1, j] - (i - 1 >= 0 ? prefix[i - 1, j] : 0); } // Check if forbidden character is // present, then continue if (sub.count[X - 'a'] != 0) { continue; } // If already present in Dictionary if (map.ContainsKey(sub)) { found = true; // Print the substrings Console.WriteLine(s.Substring(map[sub], k) + " " + s.Substring(i, k)); break; } else { map[sub] = i; } } // If no such substring is found if (!found) { Console.WriteLine("-1"); } } // Driver Code static void Main(string[] args) { string s = "rotator"; int n = s.Length; char X = 'a'; int k = 3; CheckForAnagrams(s, n, X, k); }}} |
Javascript
function Substring() { this.count = new Array(26).fill(0);}Substring.prototype.hash = function() { let hash = 0; for (let i = 0; i < 26; i++) { hash += (i + 1) * this.count[i]; hash %= 1000000007; } return hash;}Substring.prototype.equals = function(other) { if (this === other) { return true; } if (!(other instanceof Substring)) { return false; } let ob = other; for (let i = 0; i < 26; i++) { if (ob.count[i] !== this.count[i]) { return false; } } return true;}function checkForAnagrams(s, n, X, k) { let found = false; // Prefix array to store frequencies of characters let prefix = new Array(n + 1); for (let i = 0; i <= n; i++) { prefix[i] = new Array(26).fill(0); } for (let i = 0; i < n; i++) { prefix[i][s.charCodeAt(i) - 97]++; } // Generate prefix sum for (let i = 1; i < n; i++) { for (let j = 0; j < 26; j++) { prefix[i][j] += prefix[i - 1][j]; } } // Map to store frequencies of substrings let map = new Map(); // Check for anagrams for (let i = 0; i < n; i++) { if (i + k > n) { break; } // Generate frequencies of characters // of substring starting from i let sub = new Substring(); for (let j = 0; j < 26; j++) { sub.count[j] = prefix[i + k - 1][j] - ((i - 1 >= 0) ? prefix[i - 1][j] : 0); } // Check if forbidden character is present, then continue if (sub.count[X.charCodeAt(0) - 97] !== 0) { continue; } // If already present in Map if (map.has(sub.hash())) { found = true; // Print the substrings console.log(s.substring(map.get(sub.hash()), map.get(sub.hash()) + k), s.substring(i, i + k)); break; } else { map.set(sub.hash(), i); } } // If no such substring is found if (!found) { console.log("-1"); }}let s = "rotator";let n = s.length;let X = 'a';let k = 3;checkForAnagrams(s, n, X, k); |
Output:
rot tor
Time Complexity: O(N*26)
Auxiliary Space: O(N*26)
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!
