Given an array of string and a string K, the task is to find the rank of the given string if we generate all the combinations of the given array of strings.
Examples:
Input: string = [‘ab’, ‘pq’, ‘nm’], K = ‘pqnm’
Output: 7
Explanation: All combination generated are :-
” ——————-> rank 1
‘ab’ —————–> rank 2
‘pq’ —————–> rank 3
‘nm’ —————-> rank 4
‘abpq’ ————–> rank 5
‘abnm’ ————–> rank 6
‘pqnm’ ————–> rank 7
‘abpqnm’ ————> rank 8‘pqnm’ is at rank is generated at rank 7
Input: string = [‘a’, ‘b’], K = ‘aa’
Output: -1
Explanation: ‘aa’ cannot be generated by any combination of given element.
Approach: To solve the problem follow the below idea:
Generates the powerset of a given list of strings using the combinations function from the itertools module and a nested loop. It then calculates the rank of a target string in that powerset using the index function and returns -1 if the target string is not in the powerset. The code defines a list of strings and a target string, calls the get_rank function, and prints the rank.
Below are the steps for the above approach:
- Import the combinations function from the itertools module.
- Define a function to generate the powerset of a given list of strings.
- Initialize the powerset with an empty string.
- Loop over all possible lengths of subsets from 1 to the length of the input list.
- Use the combinations function to generate all possible subsets of the current length.
- Join the elements of each combination into a single string and append it to the powerset.
- Return the final powerset.
- Define a function to get the rank of a given string in the powerset of a list of strings.
- Generate the powerset of the input string list using the get_powerset function.
- If the target string is not in the powerset, return -1.
- Otherwise, return the index of the target string in the sorted powerset, plus 1.
- Get the rank of the target string in the powerset of the input string list using the get_rank function.
- Print the rank.
Below is the code for the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Define a function to generate the// powerset of a given list of stringsvector<string> get_powerset(vector<string> string_list){ // Initialize the powerset with // the empty string vector<string> powerset = { "" }; // Loop over all possible // lengths of subsets for (int i = 1; i <= string_list.size(); i++) { // Generate all combinations // of subsets of length i vector<bool> bitmask(i, true); bitmask.resize(string_list.size(), false); do { string subset = ""; for (int j = 0; j < string_list.size(); j++) { if (bitmask[j]) { subset += string_list[j]; } } // Add the generated subset to the powerset powerset.push_back(subset); } while (prev_permutation(bitmask.begin(), bitmask.end())); } // Return the final powerset return powerset;}// Define a function to get the rank// of a given string in the powerset// of a list of stringsint get_rank(vector<string> string_list, string k){ // Generate the powerset of // the input string list vector<string> powerset = get_powerset(string_list); // If the target string is not // in the powerset, return -1 if (find(powerset.begin(), powerset.end(), k) == powerset.end()) { return -1; } // Otherwise, return the index of // the target string in the // sorted powerset, plus 1 return distance(powerset.begin(), lower_bound(powerset.begin(), powerset.end(), k)) + 1;}int main(){ vector<string> string_list = { "ab", "pq", "nm" }; string k = "pqnm"; // Get the rank of the target string // in the powerset of the // input string list int rank = get_rank(string_list, k); // Print the rank cout << rank << endl; return 0;} |
Java
// Java code for the approachimport java.util.*;public class GFG { // Define a function to generate the // powerset of a given list of strings public static List<String> get_powerset(List<String> string_list) { // Initialize the powerset with // the empty string List<String> powerset = new ArrayList<>(); powerset.add(""); // Loop over all possible // lengths of subsets for (int i = 1; i <= string_list.size(); i++) { for (List<String> combination : combinations(string_list, i)) { String subset = String.join("", combination); powerset.add(subset); } } // Return the final powerset return powerset; } // Define a function to get the rank // of a given string in the powerset // of a list of strings public static int get_rank(List<String> string_list, String k) { // Generate the powerset of // the input string list List<String> powerset = get_powerset(string_list); // If the target string is not // in the powerset, return -1 if (!powerset.contains(k)) { return -1; } // Otherwise, return the index of // the target string in the // sorted powerset, plus 1 return powerset.indexOf(k) + 1; } public static <T> Iterable<List<T>> combinations(List<T> items, int n) { if (n == 0) { return Collections.singletonList(Collections.emptyList()); } else { List<List<T>> result = new ArrayList<>(); for (int i = 0; i <= items.size() - n; i++) { T item = items.get(i); for (List<T> combination : combinations(items.subList(i+1, items.size()), n-1)) { List<T> list = new ArrayList<>(); list.add(item); list.addAll(combination); result.add(list); } } return result; } } public static void main(String[] args) { List<String> string_list = Arrays.asList("ab", "pq", "nm"); String k = "pqnm"; // Get the rank of the target string // in the powerset of the // input string list int rank = get_rank(string_list, k); System.out.println(rank); // Output: 7 }} |
Python
# Import the combinations function# from the itertools modulefrom itertools import combinations# Define a function to generate the# powerset of a given list of stringsdef get_powerset(string_list): # Initialize the powerset with # the empty string powerset = [''] # Loop over all possible # lengths of subsets for i in range(1, len(string_list)+1): # Generate all combinations # of subsets of length i for combination in combinations(string_list, i): # Join the elements of each # combination into a single string powerset.append(''.join(combination)) # Return the final powerset return powerset# Define a function to get the rank# of a given string in the powerset# of a list of stringsdef get_rank(string_list, k): # Generate the powerset of # the input string list powerset = get_powerset(string_list) # If the target string is not # in the powerset, return -1 if k not in powerset: return -1 # Otherwise, return the index of # the target string in the # sorted powerset, plus 1 return powerset.index(k) + 1# Define a list of strings# and a target stringstring_list = ['ab', 'pq', 'nm']k = 'pqnm'# Get the rank of the target string# in the powerset of the# input string listrank = get_rank(string_list, k)# Print the rankprint(rank) |
C#
// C# code for the approachusing System;using System.Collections.Generic;using System.Linq;public class GFG { // Define a function to generate the // powerset of a given list of strings public static List<string> get_powerset(List<string> string_list) { // Initialize the powerset with // the empty string List<string> powerset = new List<string>(); powerset.Add(""); // Loop over all possible // lengths of subsets for (int i = 1; i <= string_list.Count; i++) { foreach(List<string> combination in combinations(string_list, i)) { string subset = string.Join("", combination); powerset.Add(subset); } } // Return the final powerset return powerset; } // Define a function to get the rank // of a given string in the powerset // of a list of strings public static int get_rank(List<string> string_list, string k) { // Generate the powerset of // the input string list List<string> powerset = get_powerset(string_list); // If the target string is not // in the powerset, return -1 if (!powerset.Contains(k)) { return -1; } // Otherwise, return the index of // the target string in the // sorted powerset, plus 1 return powerset.IndexOf(k) + 1; } public static IEnumerable<IEnumerable<T> > combinations<T>(IEnumerable<T> items, int n) { if (n == 0) { return new[] { Enumerable.Empty<T>() }; } else { List<List<T> > result = new List<List<T> >(); for (int i = 0; i <= items.Count() - n; i++) { T item = items.ElementAt(i); foreach(IEnumerable<T> combination in combinations(items.Skip(i + 1), n - 1)) { List<T> list = new List<T>(); list.Add(item); list.AddRange(combination); result.Add(list); } } return result; } } public static void Main() { List<string> string_list = new List<string>() { "ab", "pq", "nm" }; string k = "pqnm"; // Get the rank of the target string // in the powerset of the // input string list int rank = get_rank(string_list, k); Console.WriteLine(rank); // Output: 7 }}// This code is contributed by user_dtewbxkn77n |
Javascript
// Define a function to generate the// powerset of a given list of stringsfunction getPowerset(stringList) { // Initialize the powerset with //the empty string let powerset = [""]; // Loop over all possible //lengths of subsets for (let i = 1; i <= stringList.length; i++) { // Generate all combinations // of subsets of length i let bitmask = new Array(i).fill(true); bitmask = bitmask.concat(new Array(stringList.length - i).fill(false)); do { let subset = ""; for (let j = 0; j < stringList.length; j++) { if (bitmask[j]) { subset += stringList[j]; } } // Add the generated subset to the powerset powerset.push(subset); } while (prevPermutation(bitmask)); } // Return the final powerset return powerset;}// Helper function to generate // the previous permutationfunction prevPermutation(array) { let i = array.length - 1; while (i > 0 && array[i - 1] <= array[i]) { i--; } if (i <= 0) { return false; } let j = array.length - 1; while (array[j] >= array[i - 1]) { j--; } let temp = array[i - 1]; array[i - 1] = array[j]; array[j] = temp; j = array.length - 1; while (i < j) { temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } return true;}// Define a function to get the rank // of a given string in the powerset // of a list of stringsfunction getRank(stringList, k) { // Generate the powerset of // the input string list let powerset = getPowerset(stringList); // If the target string is not // in the powerset, return -1 if (!powerset.includes(k)) { return -1; } // Otherwise, return the index of // the target string in the // sorted powerset, plus 1 return powerset.indexOf(k) + 1;}// Mainlet stringList = ["ab", "pq", "nm"];let k = "pqnm";// Get the rank of the target string // in the powerset of the // input string listlet rank = getRank(stringList, k);// Print the rankconsole.log(rank); |
Output
7
Time complexity: O(n * 2n * log(n)) to generate the power set O(2n), sorting the power set O(n * 2n * log(n)) and finding the index O(n * 2n).
Auxiliary space: O(2n) to store all generated combinations.
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!
Share your thoughts in the comments
