Check if a String contains Anagrams of length K which does not contain the character X

Last Updated : 28 Mar, 2023

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 = “geeksforgeeks”, X = ‘f’, K = 5
Output: geeks geeks
Explanation:
Substrings “geeks” and “geeks” 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 1000000007
 
using namespace std;
 
// Class to represent a Substring
// in terms of frequency of
// characters present in it
class 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 anagrams
void 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 Code
int 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 approach
import java.util.*;
 
// Class to represent a Substring
// in terms of frequency of
// characters present in it
class 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 approach
import sys
MOD = 1000000007
 
# Class to represent a Substring
# in terms of frequency of
# characters present in it
class 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 anagrams
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
 
namespace Anagrams {
// Class to represent a Substring
// in terms of frequency of
// characters present in it
class 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);