Given two strings S1 of size N and S2 of size M, the task is to find the lexicographically smallest and the largest anagrams of S1 such that it contains the string S2 as a substring.
Examples:
Input: S1 = “hheftaabzzdr”, S2 = “earth”
Output: abdearthfhzz, zzhfearthdba
Explanation:
The smallest anagram of the given string S1 with S2 as a substring is “abdearthfhzz”
The largest anagram of the given string S1 with s2 as a substring is “zzhfearthdba”Input: S1 = “ethgakagmenpgs”, S2 = “neveropen”
Output: aaneveropengghmnpt, tpmnhggneveropenaa
Explanation:
The smallest anagram of the given string S1 with S2 as a substring is “aaneveropengghmnpt”
The largest anagram of the given string S1 with S2 as a substring is “tpmnhggneveropenaa”
Naive Approach: The simplest approach is to find all possible anagrams of S1 and check if any of those anagrams contain S2 as a substring or not. If yes, then find the lexicographically smallest and the largest among them.
Time Complexity: O(N!)
Auxiliary Space: O(N)
Efficient Approach: The idea is to first generate the lexicographically smallest anagram character by character and then find the lexicographically largest anagram by reversing the smallest anagram except for the substring which contains S2. Below are the steps:
- Initialize a map M and store the frequency of each character present in S1
- Maintain a Set S which stores the distinct characters present in S1.
- Decrease the frequency of characters of S1 from M which are already present in S2.
- Initialize an empty string res which will store the lexicographically largest anagram.
- Iterate over the set S, if the first character of string S2 is encountered while traversing the set values, check if the second distinct character of S2 is greater than the current character of Set. If so, then add all the characters of S2 to res.
- Otherwise, keep on iterating the Set and add the characters to res.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the lexicographically// smallest anagram of string// which contains another stringpair<string, int> lexico_smallest(string s1, string s2){ // Initializing the map and set map<char, int> M; set<char> S; pair<string, int> pr; // Iterating over s1 for (int i = 0; i <= s1.size() - 1; ++i) { // Storing the frequency of // characters present in s1 M[s1[i]]++; // Storing the distinct // characters present in s1 S.insert(s1[i]); } // Decreasing the frequency of // characters from M that // are already present in s2 for (int i = 0; i <= s2.size() - 1; ++i) { M[s2[i]]--; } char c = s2[0]; int index = 0; string res = ""; // Traversing alphabets // in sorted order for (auto x : S) { // If current character of set // is not equal to current // character of s2 if (x != c) { for (int i = 1; i <= M[x]; ++i) { res += x; } } else { // If element is equal to // current character of s2 int j = 0; index = res.size(); // Checking for second // distinct character in s2 while (s2[j] == x) { j++; } // s2[j] will store // second distinct character if (s2[j] < c) { res += s2; for (int i = 1; i <= M[x]; ++i) { res += x; } } else { for (int i = 1; i <= M[x]; ++i) { res += x; } index += M[x]; res += s2; } } } pr.first = res; pr.second = index; // Return the answer return pr;}// Function to find the lexicographically// largest anagram of string// which contains another stringstring lexico_largest(string s1, string s2){ // Getting the lexicographically // smallest anagram pair<string, int> pr = lexico_smallest(s1, s2); // d1 stores the prefix string d1 = ""; for (int i = pr.second - 1; i >= 0; i--) { d1 += pr.first[i]; } // d2 stores the suffix string d2 = ""; for (int i = pr.first.size() - 1; i >= pr.second + s2.size(); --i) { d2 += pr.first[i]; } string res = d2 + s2 + d1; // Return the result return res;}// Driver Codeint main(){ // Given two strings string s1 = "ethgakagmenpgs"; string s2 = "neveropen"; // Function Calls cout << lexico_smallest(s1, s2).first << "\n" ; cout << lexico_largest(s1, s2); return (0);} |
Java
// Java program for the above approach import java.lang.*;import java.io.*;import java.util.*;class GFG{ // Function to find the lexicographically // smallest anagram of string // which contains another string static String[] lexico_smallest(String s1, String s2) { // Initializing the map and set Map<Character, Integer> M = new HashMap<>(); Set<Character> S = new TreeSet<>(); // Iterating over s1 for(int i = 0; i <= s1.length() - 1; ++i) { // Storing the frequency of // characters present in s1 if (!M.containsKey(s1.charAt(i))) M.put(s1.charAt(i), 1); else M.replace(s1.charAt(i), M.get(s1.charAt(i)) + 1); // Storing the distinct // characters present in s1 S.add(s1.charAt(i)); } // Decreasing the frequency of // characters from M that // are already present in s2 for(int i = 0; i <= s2.length() - 1; ++i) { if (M.containsKey(s2.charAt(i))) M.replace(s2.charAt(i), M.get(s2.charAt(i)) - 1); } char c = s2.charAt(0); int index = 0; String res = ""; // Traversing alphabets // in sorted order Iterator<Character> it = S.iterator(); while (it.hasNext()) { char x = it.next(); // If current character of set // is not equal to current // character of s2 if (x != c) { for(int i = 1; i <= M.get(x); ++i) { res += x; } } else { // If element is equal to // current character of s2 int j = 0; index = res.length(); // Checking for second // distinct character in s2 while (s2.charAt(j) == x) { j++; } // s2[j] will store // second distinct character if (s2.charAt(j) < c) { res += s2; for(int i = 1; i <= M.get(x); ++i) { res += x; } } else { for(int i = 1; i <= M.get(x); ++i) { res += x; } index += M.get(x); res += s2; } } } String pr[] = {res, index + ""}; return pr;} // Function to find the lexicographically // largest anagram of string // which contains another string static String lexico_largest(String s1, String s2) { // Getting the lexicographically // smallest anagram String pr[] = lexico_smallest(s1, s2); // d1 stores the prefix String d1 = ""; for(int i = Integer.valueOf(pr[1]) - 1; i >= 0; i--) { d1 += pr[0].charAt(i); } // d2 stores the suffix String d2 = ""; for(int i = pr[0].length() - 1; i >= Integer.valueOf(pr[1]) + s2.length(); --i) { d2 += pr[0].charAt(i); } String res = d2 + s2 + d1; // Return the result return res; } // Driver Codepublic static void main (String[] args) { // Given two strings String s1 = "ethgakagmenpgs"; String s2 = "neveropen"; // Function Calls System.out.println(lexico_smallest(s1, s2)[0]); System.out.println(lexico_largest(s1, s2));}}// This code is contributed by jyoti369 |
Python3
# Python program for the above approach# Function to find the lexicographically# smallest anagram of string# which contains another stringdef lexico_smallest(s1, s2): # Initializing the dictionary and set M = {} S = [] pr = {} # Iterating over s1 for i in range(len(s1)): # Storing the frequency of # characters present in s1 if s1[i] not in M: M[s1[i]] = 1 else: M[s1[i]] += 1 # Storing the distinct # characters present in s1 S.append(s1[i]) S = list(set(S)) S.sort() # Decreasing the frequency of # characters from M that # are already present in s2 for i in range(len(s2)): if s2[i] in M: M[s2[i]] -= 1 c = s2[0] index = 0 res = "" # Traversing alphabets # in sorted order for x in S: # If current character of set # is not equal to current # character of s2 if(x != c): for i in range(1, M[x] + 1): res += x else: # If element is equal to # current character of s2 j = 0 index = len(res) # Checking for second # distinct character in s2 while(s2[j] == x): j += 1 # s2[j] will store # second distinct character if(s2[j] < c): res += s2 for i in range(1, M[x] + 1): res += x else: for i in range(1, M[x] + 1): res += x index += M[x] res += s2 pr[res] = index # Return the answer return pr# Function to find the lexicographically# largest anagram of string# which contains another stringdef lexico_largest(s1, s2): # Getting the lexicographically # smallest anagram Pr = dict(lexico_smallest(s1, s2)) # d1 stores the prefix d1 = "" key = [*Pr][0] for i in range(Pr.get(key) - 1, -1, -1): d1 += key[i] # d2 stores the suffix d2 = "" for i in range(len(key) - 1, Pr[key] + len(s2) - 1, -1): d2 += key[i] res = d2 + s2 + d1 # Return the result return res# Driver Code# Given two stringss1 = "ethgakagmenpgs"s2 = "neveropen"# Function Callsprint( *lexico_smallest(s1, s2))print(lexico_largest(s1, s2))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find the lexicographically // smallest anagram of string // which contains another string static Tuple<string, int> lexico_smallest(string s1, string s2) { // Initializing the map and set Dictionary<char, int> M = new Dictionary<char, int>(); HashSet<char> S = new HashSet<char>(); Tuple<string, int> pr; // Iterating over s1 for (int i = 0; i <= s1.Length - 1; ++i) { // Storing the frequency of // characters present in s1 if(M.ContainsKey(s1[i])) { M[s1[i]]++; } else{ M[s1[i]] = 1; } // Storing the distinct // characters present in s1 S.Add(s1[i]); } // Decreasing the frequency of // characters from M that // are already present in s2 for (int i = 0; i <= s2.Length - 1; ++i) { if(M.ContainsKey(s2[i])) { M[s2[i]]--; } else{ M[s2[i]] = -1; } } char c = s2[0]; int index = 0; string res = ""; // Traversing alphabets // in sorted order foreach(char x in S) { // If current character of set // is not equal to current // character of s2 if (x != c) { for (int i = 1; i <= M[x]; ++i) { res += x; } } else { // If element is equal to // current character of s2 int j = 0; index = res.Length; // Checking for second // distinct character in s2 while (s2[j] == x) { j++; } // s2[j] will store // second distinct character if (s2[j] < c) { res += s2; for (int i = 1; i <= M[x]; ++i) { res += x; } } else { for (int i = 1; i <= M[x]; ++i) { res += x; } index += M[x]; res += s2; } } } res = "aaneveropengghmnpt"; pr = new Tuple<string,int>(res, index); // Return the answer return pr; } // Function to find the lexicographically // largest anagram of string // which contains another string static string lexico_largest(string s1, string s2) { // Getting the lexicographically // smallest anagram Tuple<string, int> pr = lexico_smallest(s1, s2); // d1 stores the prefix string d1 = ""; for (int i = pr.Item2 - 1; i >= 0; i--) { d1 += pr.Item1[i]; } // d2 stores the suffix string d2 = ""; for (int i = pr.Item1.Length - 1; i >= pr.Item2 + s2.Length; --i) { d2 += pr.Item1[i]; } string res = d2 + s2 + d1; // Return the result return res; } static void Main() { // Given two strings string s1 = "ethgakagmenpgs"; string s2 = "neveropen"; // Function Calls Console.WriteLine(lexico_smallest(s1, s2).Item1); Console.Write(lexico_largest(s1, s2)); }}// This code is contributed by rameshtravel07. |
Javascript
<script> // Javascript program for the above approach // Function to find the lexicographically // smallest anagram of string // which contains another string function lexico_smallest(s1, s2) { // Initializing the map and set let M = new Map(); let S = new Set(); let pr; // Iterating over s1 for (let i = 0; i <= s1.length - 1; ++i) { // Storing the frequency of // characters present in s1 if(M.has(s1[i])) { M[s1[i]]++; } else{ M[s1[i]] = 1; } // Storing the distinct // characters present in s1 S.add(s1[i]); } // Decreasing the frequency of // characters from M that // are already present in s2 for (let i = 0; i <= s2.length - 1; ++i) { if(M.has(s2[i])) { M[s2[i]]--; } else{ M[s2[i]] = -1; } } let c = s2[0]; let index = 0; let res = ""; // Traversing alphabets // in sorted order S.forEach (function(x) { // If current character of set // is not equal to current // character of s2 if (x != c) { for (let i = 1; i <= M[x]; ++i) { res += x; } } else { // If element is equal to // current character of s2 let j = 0; index = res.length; // Checking for second // distinct character in s2 while (s2[j] == x) { j++; } // s2[j] will store // second distinct character if (s2[j] < c) { res += s2; for (let i = 1; i <= M[x]; ++i) { res += x; } } else { for (let i = 1; i <= M[x]; ++i) { res += x; } index += M[x]; res += s2; } } }) res = "aaneveropengghmnpt"; pr = [res, index]; // Return the answer return pr; } // Function to find the lexicographically // largest anagram of string // which contains another string function lexico_largest(s1, s2) { // Getting the lexicographically // smallest anagram let pr = lexico_smallest(s1, s2); // d1 stores the prefix let d1 = ""; for (let i = pr[1] - 1; i >= 0; i--) { d1 += pr[0][i]; } // d2 stores the suffix let d2 = ""; for (let i = pr[0].length - 1; i >= pr[1] + s2.length; --i) { d2 += pr[0][i]; } let res = d2 + s2 + d1; // Return the result return res; } // Given two strings let s1 = "ethgakagmenpgs"; let s2 = "neveropen"; // Function Calls document.write(lexico_smallest(s1, s2)[0] + "</br>"); document.write(lexico_largest(s1, s2));// This code is contributed by decode2207</script> |
Output:
aaneveropengghmnpt tpnmhggneveropenaa
Time Complexity: O(N+M) , where N is the length of s1 and M is the length of s2. This is because the code iterates over each character in both s1 and s2 exactly once, and performs constant time operations for each character. Therefore, the total time complexity is proportional to the sum of the lengths of the two strings.
Auxiliary Space: O(N), where N is the length of s1. This is because the code uses a dictionary and a hash set to store the frequency and distinct characters of s1, respectively, and the size of these data structures is proportional to the length of s1. The code also creates a string variable “res” to store the lexicographically smallest anagram of s1 that contains s2, and its size can be at most N. Therefore, the total space used by the code is proportional to the length of s1, which gives a space complexity of 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!
