Given a string str and an array of strings arr[], the task is to check if the given string can be formed by any of the string pairs from the array or their permutations.
Examples:
Input: str = “amazon”, arr[] = {“loa”, “azo”, “ft”, “amn”, “lka”}
Output: Yes
The chosen strings are “amn” and “azo”
which can be rearranged as “amazon”.Input: str = “neveropen”, arr[] = {“neveropen”, “geek”, “for”}
Output: No
Method 1: We sort the given string first, then run two nested loops and select two strings from the given array at a time and concatenate them and then sort the resultant string.
After sorting, we check if it is equal to our given sorted string.
Time complexity: O(nlogn+m2klogk) where n is the size of the given string, m is the size of the given array, and k is the maximum size obtained by adding any two strings (which is basically the sum of the size of the two longest strings in the given array).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if str can be// generated from any permutation of the// two strings selected from the given vectorbool isPossible(vector<string> v, string str){ // Sort the given string sort(str.begin(), str.end()); // Select two strings at a time from given vector for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size(); j++) { // Get the concatenated string string temp = v[i] + v[j]; // Sort the resultant string sort(temp.begin(), temp.end()); // If the resultant string is equal // to the given string str if (temp.compare(str) == 0) { return true; } } } // No valid pair found return false;}// Driver codeint main(){ string str = "amazon"; vector<string> v{ "fds", "oxq", "zoa", "epw", "amn" }; if (isPossible(v, str)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function that returns true if str can be// generated from any permutation of the// two strings selected from the given vectorstatic boolean isPossible(Vector<String> v, String str){ // Sort the given string str = sortString(str); // Select two strings at a time from given vector for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size(); j++) { // Get the concatenated string String temp = v.get(i) + v.get(j); // Sort the resultant string temp = sortString(temp); // If the resultant string is equal // to the given string str if (temp.compareTo(str) == 0) { return true; } } } // No valid pair found return false;}// Method to sort a string alphabetically public 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 = "amazon"; String []arr = { "fds", "oxq", "zoa", "epw", "amn" }; Vector<String> v = new Vector<String>(Arrays.asList(arr)); if (isPossible(v, str)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function that returns true if str can be # generated from any permutation of the # two strings selected from the given vector def isPossible(v, string ) : char_list = list(string) # Sort the given string char_list.sort() # Select two strings at a time from given vector for i in range(len(v)-1) : for j in range(len(v)) : # Get the concatenated string temp = v[i] + v[j]; # Sort the resultant string temp_list = list(temp) temp_list.sort() # If the resultant string is equal # to the given string str if (temp_list == char_list) : return True; # No valid pair found return False; # Driver code if __name__ == "__main__" : string = "amazon"; v = [ "fds", "oxq", "zoa", "epw", "amn" ]; if (isPossible(v, string)): print("Yes"); else : print("No"); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG {// Function that returns true if str can be// generated from any permutation of the// two strings selected from the given vectorstatic Boolean isPossible(List<String> v, String str){ // Sort the given string str = sortString(str); // Select two strings at a time from given vector for (int i = 0; i <v.Count - 1; i++) { for (int j = i + 1; j <v.Count; j++) { // Get the concatenated string String temp = v[i] + v[j]; // Sort the resultant string temp = sortString(temp); // If the resultant string is equal // to the given string str if (temp.CompareTo(str) == 0) { return true; } } } // No valid pair found return false;}// Method to sort a string alphabetically public 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 = "amazon"; String []arr = { "fds", "oxq", "zoa", "epw", "amn" }; List<String> v = new List<String>(arr); if (isPossible(v, str)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if str can be// generated from any permutation of the// two strings selected from the given vectorfunction isPossible(v, str){ // Sort the given string str = str.split('').sort().join(''); // Select two strings at a time from given vector for (var i = 0; i < v.length - 1; i++) { for (var j = i + 1; j < v.length; j++) { // Get the concatenated string var temp = v[i] + v[j]; // Sort the resultant string temp = temp.split('').sort().join(''); // If the resultant string is equal // to the given string str if (temp === (str)) { return true; } } } // No valid pair found return false;}// Driver codevar str = "amazon";var v = ["fds", "oxq", "zoa", "epw", "amn"];if (isPossible(v, str)) document.write( "Yes");else document.write( "No");</script> |
Output:
Yes
Time Complexity: O(n2)
Auxiliary Space: O(x) where x is the maximum length of two input strings after concatenating
Method 2: Counting sort can be used to reduce the running time of the above approach. Counting sort uses a table to store the count of each character. We have 26 alphabets, hence we make an array of size 26 to store counts of each character in the string. Then take the characters in increasing order to get the sorted string.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 26// Function to sort the given string// using counting sortvoid countingsort(string& s){ // Array to store the count of each character int count[MAX] = { 0 }; for (int i = 0; i < s.length(); i++) { count[s[i] - 'a']++; } int index = 0; // Insert characters in the string // in increasing order for (int i = 0; i < MAX; i++) { int j = 0; while (j < count[i]) { s[index++] = i + 'a'; j++; } }}// Function that returns true if str can be// generated from any permutation of the// two strings selected from the given vectorbool isPossible(vector<string> v, string str){ // Sort the given string countingsort(str); // Select two strings at a time from given vector for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size(); j++) { // Get the concatenated string string temp = v[i] + v[j]; // Sort the resultant string countingsort(temp); // If the resultant string is equal // to the given string str if (temp.compare(str) == 0) { return true; } } } // No valid pair found return false;}// Driver codeint main(){ string str = "amazon"; vector<string> v{ "fds", "oxq", "zoa", "epw", "amn" }; if (isPossible(v, str)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG {static int MAX = 26; // Function to sort the given string // using counting sort static String countingsort(char[] s) { // Array to store the count of each character int []count = new int[MAX]; for (int i = 0; i < s.length; i++) { count[s[i] - 'a']++; } int index = 0; // Insert characters in the string // in increasing order for (int i = 0; i < MAX; i++) { int j = 0; while (j < count[i]) { s[index++] = (char)(i + 'a'); j++; } } return String.valueOf(s);} // Function that returns true if str can be // generated from any permutation of the // two strings selected from the given vector static boolean isPossible(Vector<String> v, String str) { // Sort the given string str=countingsort(str.toCharArray()); // Select two strings at a time from given vector for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size(); j++) { // Get the concatenated string String temp = v.get(i) + v.get(j); // Sort the resultant string temp = countingsort(temp.toCharArray()); // If the resultant string is equal // to the given string str if (temp.equals(str)) { return true; } } } // No valid pair found return false; } // Driver code public static void main(String[] args) { String str = "amazon"; String []arr = { "fds", "oxq", "zoa", "epw", "amn" }; Vector<String> v = new Vector<String>(Arrays.asList(arr)); if (isPossible(v, str)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 implementation of the approachMAX = 26# Function to sort the given string# using counting sortdef countingsort(s): # Array to store the count of each character count = [0 for i in range(MAX)] for i in range(len(s)): count[ord(s[i]) - ord('a')] += 1 index = 0 # Insert characters in the string # in increasing order for i in range(MAX): j = 0 while (j < count[i]): s = s.replace(s[index],chr(97+i)) index += 1 j += 1 # Function that returns true if str can be# generated from any permutation of the# two strings selected from the given vectordef isPossible(v, str1): # Sort the given string countingsort(str1); # Select two strings at a time from given vector for i in range(len(v)-1): for j in range(i + 1,len(v),1): # Get the concatenated string temp = v[i] + v[j] # Sort the resultant string countingsort(temp) # If the resultant string is equal # to the given string str if (temp == str1): return False # No valid pair found return True# Driver codeif __name__ == '__main__': str1 = "amazon" v = ["fds", "oxq", "zoa", "epw", "amn"] if (isPossible(v, str1)): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the above approach using System;using System.Collections.Generic; class GFG {static int MAX = 26; // Function to sort the given string // using counting sort static String countingsort(char[] s) { // Array to store the count of each character int []count = new int[MAX]; for (int i = 0; i < s.Length; i++) { count[s[i] - 'a']++; } int index = 0; // Insert characters in the string // in increasing order for (int i = 0; i < MAX; i++) { int j = 0; while (j < count[i]) { s[index++] = (char)(i + 'a'); j++; } } return String.Join("", s);} // Function that returns true if str can be // generated from any permutation of the // two strings selected from the given vector static Boolean isPossible(List<String> v, String str) { // Sort the given string str = countingsort(str.ToCharArray()); // Select two strings at a time from given vector for (int i = 0; i < v.Count - 1; i++) { for (int j = i + 1; j < v.Count; j++) { // Get the concatenated string String temp = v[i] + v[j]; // Sort the resultant string temp = countingsort(temp.ToCharArray()); // If the resultant string is equal // to the given string str if (temp.Equals(str)) { return true; } } } // No valid pair found return false; } // Driver code public static void Main(String[] args) { String str = "amazon"; String []arr = { "fds", "oxq", "zoa", "epw", "amn" }; List<String> v = new List<String>(arr); if (isPossible(v, str)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach let MAX = 26; // Function to sort the given string // using counting sort function countingsort(s) { // Array to store the count of each character let count = new Array(MAX); count.fill(0); for (let i = 0; i < s.length; i++) { count[s[i].charCodeAt() - 'a'.charCodeAt()]++; } let index = 0; // Insert characters in the string // in increasing order for (let i = 0; i < MAX; i++) { let j = 0; while (j < count[i]) { s[index++] = String.fromCharCode(i + 'a'.charCodeAt()); j++; } } return s.join(""); } // Function that returns true if str can be // generated from any permutation of the // two strings selected from the given vector function isPossible(v, str) { // Sort the given string str = countingsort(str.split('')); // Select two strings at a time from given vector for (let i = 0; i < v.length - 1; i++) { for (let j = i + 1; j < v.length; j++) { // Get the concatenated string let temp = v[i] + v[j]; // Sort the resultant string temp = countingsort(temp.split('')); // If the resultant string is equal // to the given string str if (temp == str) { return true; } } } // No valid pair found return false; } let str = "amazon"; let v = [ "fds", "oxq", "zoa", "epw", "amn" ]; if (isPossible(v, str)) document.write("Yes"); else document.write("No");</script> |
Output:
Yes
Time complexity: O(n+m2k) where n is the size of the given string, m is the size of the given array, and k is the maximum size obtained by adding any two strings (which is basically the sum of the size of the two longest strings in the given array).
Auxiliary Space: O(x) where x is the maximum length of two input strings after concatenating
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!
