Given an array arr[] of N strings. Let X and Y be two strings, X and Y are said to be valid pairs if the rearrangement of the resultant string from the concatenation of X with X (i.e., X+X) gives Y. The task is to count the number of such valid pairs.
Examples:
Input: N = 4, arr[] = {“hacker”, ”ackerhackerh”, ”int”, ”iittnn”, ”long”}
Output: 2
Explanation:
Pair {“hacker”, ”ackerhackerh”} “hacker” When concatenated with “hacker” gives ”ackerhackerh” after rearrangement.
Pair {“int”, ”iittnn”} “int” When concatenated with “int” gives ”iittnn” after rearrangement.Input: N = 3, arr[] = {“easy”, ”yeasseay“, “medium“}
Output:1
Explanation:
Pair {“easy”, ”yeasseay“} “easy” When concatenated with “easy” gives ”yeasseay“ after rearrangement.
Naive Approach: The idea is to generate all possible pairs and check if any pairs form a valid pair as per the given condition or not. If yes then count this pair and check for the next pair. Print the value of count after the above steps.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to store the sorted string in Hashmap along with its count and iterate through each string of the array concatenate it with itself and find its count in Hashmap add it to the count of pairs. Below are the steps:
- Create a hashmap.
- Sort the given strings in the array and store their count in hashmap.
- Again iterate through all strings and concatenate each string with itself sort the string and find its count in Hashmap.
- Update the final count in the above step and print the final count after all the above steps.
Below is the implementation of the above approach:
C++14
// C++14 program for the above approach#include<bits/stdc++.h>using namespace std;// Function to implement sorting on// stringsstring sorted(string s){ // Convert string to char array char ch[s.length()]; for(int i = 0; i < s.length(); i++) { ch[i] = s[i]; } // Sort the array sort(ch, ch + s.length()); string sb; for(char c : ch) sb += c; // Return string return sb;}// Function that count total number// of valid pairsint countPairs(string arr[], int N){ // Create hashmap to store the // frequency of each string // in sorted form map<string, int> mp; // Initialise the count of pairs int count = 0; for(int i = 0; i < N; i++) { // Store each string in sorted // form along with it's count string s = sorted(arr[i]); mp[s]++; } // Iterate through each string // in the array for(int i = 0; i < N; i++) { // Concatenate each string with itself arr[i] = arr[i] + arr[i]; sorted(arr[i]); // Find its count in the hashmap count += mp[sorted(arr[i])]; } // Return answer return count;}// Driver Codeint main(){ int N = 3; // Given array of strings string arr[] = { "easy", "yeasseay", "medium" }; // Function Call cout << countPairs(arr, N) << endl; return 0;}// This code is contributed by sallagondaavinashreddy7 |
Java
// Java program for the above approach import java.util.*; public class Main { // Function that count total number // of valid pairs public static int countPairs(String arr[], int N) { // Create hashmap to store the // frequency of each string // in sorted form HashMap<String, Integer> map = new HashMap<>(); // Initialise the count of pairs int count = 0; for (int i = 0; i < N; i++) { String s = sort(arr[i]); // Store each string in sorted // form along with it's count map.put(s, map.getOrDefault(s, 0) + 1); } // Iterate through each string // in the array for (int i = 0; i < N; i++) { // Concatenate each string with itself String s = sort(arr[i] + arr[i]); // Find its count in the hashmap count += map.getOrDefault(s, 0); } // Return answer return count; } // Function to implement sorting on // strings public static String sort(String s) { // Convert string to char array char ch[] = s.toCharArray(); // Sort the array Arrays.sort(ch); StringBuffer sb = new StringBuffer(); for (char c : ch) sb.append(c); // Return string return sb.toString(); } // Driver Code public static void main(String args[]) { int N = 3; // Given array of strings String arr[] = { "easy", "yeasseay", "medium" }; // Function Call System.out.println(countPairs(arr, N)); } } |
Python3
# Python3 program for the above approachfrom collections import defaultdict# Function that count total number# of valid pairs def countPairs(arr, N): # Create hashmap to store the # frequency of each string # in sorted form map = defaultdict(lambda : 0) # Initialise the count of pairs count = 0 for i in range(N): s = sorted(arr[i]) # Store each string in sorted # form along with it's count map["".join(s)] += 1 # Iterate through each string # in the array for i in range(N): # Concatenate each string with itself s = sorted(arr[i] + arr[i]) # Find its count in the hashmap count += map["".join(s)] # Return answer return count# Driver CodeN = 3# Given array of stringsarr = [ "easy", "yeasseay", "medium" ]# Function callprint(countPairs(arr, N))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Text; class GFG{// Function that count total number// of valid pairspublic static int countPairs(string []arr, int N){ // Create hashmap to store the // frequency of each string // in sorted form Dictionary<string, int> map = new Dictionary<string, int>(); // Initialise the count of pairs int count = 0; for(int i = 0; i < N; i++) { string s = sort(arr[i]); // Store each string in sorted // form along with it's count if (map.ContainsKey(s)) { map[s]++; } else { map[s] = 1; } } // Iterate through each string // in the array for(int i = 0; i < N; i++) { // Concatenate each string with itself string s = sort(arr[i] + arr[i]); // Find its count in the hashmap count += map.GetValueOrDefault(s, 0); } // Return answer return count;}// Function to implement sorting on// stringspublic static string sort(string s){ // Convert string to char array char []ch = s.ToCharArray(); // Sort the array Array.Sort(ch); StringBuilder sb = new StringBuilder(); foreach(char c in ch) sb.Append(c); // Return string return sb.ToString();}// Driver Codepublic static void Main(string []args){ int N = 3; // Given array of strings string []arr = { "easy", "yeasseay", "medium" }; // Function call Console.Write(countPairs(arr, N));}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program for the above approach// Function to implement sorting on// stringsfunction sorted(s){ // Convert string to char array var ch = Array(s.length); for(var i = 0; i < s.length; i++) { ch[i] = s[i]; } // Sort the array ch.sort(); var sb; ch.forEach(c => { sb += c; }); // Return string return sb;}// Function that count total number// of valid pairsfunction countPairs( arr, N){ // Create hashmap to store the // frequency of each string // in sorted form var mp = new Map(); // Initialise the count of pairs var count = 0; for(var i = 0; i < N; i++) { // Store each string in sorted // form along with it's count var s = sorted(arr[i]); if(mp.has(s)) mp.set(s, mp.get(s)+1) else mp.set(s, 1) } // Iterate through each string // in the array for(var i = 0; i < N; i++) { // Concatenate each string with itself arr[i] = arr[i] + arr[i]; sorted(arr[i]); // Find its count in the hashmap count += mp.has(sorted(arr[i]))?mp.get(sorted(arr[i])):0; } // Return answer return count;}// Driver Codevar N = 3;// Given array of stringsvar arr = ["easy", "yeasseay", "medium"];// Function Calldocument.write( countPairs(arr, N));</script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: 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!
