Given an array arr[] consisting of N strings, the task is to find the pair of strings that is not present in the array formed by any pairs (arr[i], arr[j]) by swapping the first characters of the strings arr[i] and arr[j].
Examples:
Input: arr[] = {“good”, “bad”, “food”}
Output: 2
Explanation:
The possible pairs that can be formed by swapping the first characters of any pair are:
- (“good”, “bad”): Swapping the characters ‘g’ and ‘b’, modifies the strings to “bood” and gad which is not present in the array.
- (“bad”, “food”): Swapping the characters ‘g’ and ‘b’, modifies the strings to “bood” and gad which is not present in the array.
Therefore, the total count is 2.
Input: arr[] = {“geek”, “peek”}
Output: 0
Naive Approach: The simplest approach to solve the given problem is to generate all the pairs of strings and for each pair swap the first characters of both the strings and if both the strings are present in the array then count this pair. After checking for all the pairs, print the value of the count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count new pairs of strings// that can be obtained by swapping first// characters of any pair of stringsvoid countStringPairs(string a[], int n){ // Stores the count of pairs int ans = 0; // Generate all possible pairs of // strings from the array arr[] for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Stores the current // pair of strings string p = a[i], q = a[j]; // Swap the first characters if (p[0] != q[0]) { swap(p[0], q[0]); int flag1 = 0; int flag2 = 0; // Check if they are already // present in the array or not for (int k = 0; k < n; k++) { if (a[k] == p) { flag1 = 1; } if (a[k] == q) { flag2 = 1; } } // If both the strings // are not present if (flag1 == 0 && flag2 == 0) { // Increment the ans // by 1 ans = ans + 1; } } } } // Print the resultant count cout << ans;}// Driver Codeint main(){ string arr[] = { "good", "bad", "food" }; int N = sizeof(arr) / sizeof(arr[0]); countStringPairs(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to count new pairs of strings// that can be obtained by swapping first// characters of any pair of stringsstatic void countStringPairs(String a[], int n){ // Stores the count of pairs int ans = 0; // Generate all possible pairs of // strings from the array arr[] for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // Stores the current // pair of strings char p[] = a[i].toCharArray(); char q[] = a[j].toCharArray(); // Swap the first characters if (p[0] != q[0]) { char temp = p[0]; p[0] = q[0]; q[0] = temp; int flag1 = 0; int flag2 = 0; // Check if they are already // present in the array or not for(int k = 0; k < n; k++) { if (a[k].equals(new String(p))) { flag1 = 1; } if (a[k].equals(new String(q))) { flag2 = 1; } } // If both the strings // are not present if (flag1 == 0 && flag2 == 0) { // Increment the ans // by 1 ans = ans + 1; } } } } // Print the resultant count System.out.println(ans);}// Driver Codepublic static void main(String[] args){ String arr[] = { "good", "bad", "food" }; int N = arr.length; countStringPairs(arr, N);}}// This code is contributed by Kingash |
Python3
# python 3 program for the above approach# Function to count new pairs of strings# that can be obtained by swapping first# characters of any pair of stringsdef countStringPairs(a, n): # Stores the count of pairs ans = 0 # Generate all possible pairs of # strings from the array arr[] for i in range(n): for j in range(i + 1, n, 1): # Stores the current # pair of strings p = a[i] q = a[j] # Swap the first characters if (p[0] != q[0]): p = list(p) q = list(q) temp = p[0] p[0] = q[0] q[0] = temp p = ''.join(p) q = ''.join(q) flag1 = 0 flag2 = 0 # Check if they are already # present in the array or not for k in range(n): if (a[k] == p): flag1 = 1 if (a[k] == q): flag2 = 1 # If both the strings # are not present if (flag1 == 0 and flag2 == 0): # Increment the ans # by 1 ans = ans + 1 # Print the resultant count print(ans)# Driver Codeif __name__ == '__main__': arr = ["good", "bad", "food"] N = len(arr) countStringPairs(arr, N) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C # program for the above approachusing System;class GFG { // Function to count new pairs of strings // that can be obtained by swapping first // characters of any pair of strings static void countStringPairs(string[] a, int n) { // Stores the count of pairs int ans = 0; // Generate all possible pairs of // strings from the array arr[] for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Stores the current // pair of strings char[] p = a[i].ToCharArray(); char[] q = a[j].ToCharArray(); // Swap the first characters if (p[0] != q[0]) { char temp = p[0]; p[0] = q[0]; q[0] = temp; int flag1 = 0; int flag2 = 0; // Check if they are already // present in the array or not for (int k = 0; k < n; k++) { if (a[k].Equals(new string(p))) { flag1 = 1; } if (a[k].Equals(new string(q))) { flag2 = 1; } } // If both the strings // are not present if (flag1 == 0 && flag2 == 0) { // Increment the ans // by 1 ans = ans + 1; } } } } // Print the resultant count Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { string[] arr = { "good", "bad", "food" }; int N = arr.Length; countStringPairs(arr, N); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach // Function to count new pairs of strings // that can be obtained by swapping first // characters of any pair of strings function countStringPairs(a, n) { // Stores the count of pairs var ans = 0; // Generate all possible pairs of // strings from the array arr[] for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // Stores the current // pair of strings var p = a[i]; var q = a[j]; // Swap the first characters if (p[0] !== q[0]) { p = p.split(""); q = q.split(""); var temp = p[0]; p[0] = q[0]; q[0] = temp; p = p.join(""); q = q.join(""); var flag1 = 0; var flag2 = 0; // Check if they are already // present in the array or not for (let k = 0; k < n; k++) { if (a[k] === p) flag1 = 1; if (a[k] === q) flag2 = 1; } // If both the strings // are not present if (flag1 === 0 && flag2 === 0) { // Increment the ans // by 1 ans = ans + 1; } } } } // Print the resultant count document.write(ans); } // Driver Code var arr = ["good", "bad", "food"]; var N = arr.length; countStringPairs(arr, N); </script> |
Output:
2
Time Complexity: O(N3)
Auxiliary Space: O(M), where M is the largest size of the string present in the array, A[]
Efficient Approach: The above approach can also be optimized by using the concept of Hashing. Follow the steps below to solve the problem:
- Initialize a variable, say ans as 0 to store the possible count of pairs of strings.
- Initialize a HashMap, say M to store all the strings present in the array arr[].
- Traverse the array, arr[] and increment the occurrence of arr[i] in M.
- Iterate in the range [0, N – 1] using the variable i and perform the following steps:
- Iterate in the range [i + 1, N – 1] using the variable j and perform the following steps:
- Store the current pair of strings in two temporary strings, say p and q.
- Swap the first character of strings p and q.
- If strings p and q are both not present in the HashMap, M, then increment the value of ans by 1.
- Iterate in the range [i + 1, N – 1] using the variable j and perform the following steps:
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count newly created pairs// by swapping the first characters of// any pairs of stringsvoid countStringPairs(string a[], int n){ // Stores the count all possible // pair of strings int ans = 0; // Push all the strings // into the Unordered Map unordered_map<string, int> s; for (int i = 0; i < n; i++) { s[a[i]]++; } // Generate all possible pairs of // strings from the array arr[] for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Store the current // pair of strings string p = a[i]; string q = a[j]; // Swap the first character if (p[0] != q[0]) { swap(p[0], q[0]); // Check if both string // are not present in map if (s.find(p) == s.end() && s.find(q) == s.end()) { ans++; } } } } // Print the result cout << ans;}// Driver Codeint main(){ string arr[] = { "good", "bad", "food" }; int N = sizeof(arr) / sizeof(arr[0]); countStringPairs(arr, N); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{// Function to count newly created pairs// by swapping the first characters of// any pairs of stringsstatic void countStringPairs(String a[], int n){ // Stores the count all possible // pair of strings int ans = 0; // Push all the strings // into the Unordered Map Map<String, Integer> s = new HashMap<>(); for(int i = 0; i < n; i++) { s.put(a[i], s.getOrDefault(a[i], 0)); } // Generate all possible pairs of // strings from the array arr[] for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // Store the current // pair of strings StringBuilder p = new StringBuilder(a[i]); StringBuilder q = new StringBuilder(a[j]); // Swap the first character if (p.charAt(0) != q.charAt(0)) { char t = p.charAt(0); p.setCharAt(0, q.charAt(0)); q.setCharAt(0, t); // Check if both string // are not present in map if (!s.containsKey(p.toString()) && !s.containsKey(q.toString())) { ans++; } } } } // Print the result System.out.println(ans);}// Driver codepublic static void main(String[] args){ String arr[] = {"good", "bad", "food"}; int N = arr.length; countStringPairs(arr, N);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to count newly created pairs# by swapping the first characters of# any pairs of stringsdef countStringPairs(a, n): # Stores the count all possible # pair of strings ans = 0 # Push all the strings # into the Unordered Map s = {} for i in range(n): s[a[i]] = s.get(a[i], 0) + 1 # Generate all possible pairs of # strings from the array arr[] for i in range(n): for j in range(i + 1, n): # Store the current # pair of strings p = [i for i in a[i]] q = [j for j in a[j]] # Swap the first character if (p[0] != q[0]): p[0], q[0] = q[0], p[0] # Check if both string # are not present in map if (("".join(p) not in s) and ("".join(q) not in s)): ans += 1 # Print the result print (ans)# Driver Codeif __name__ == '__main__': arr = [ "good", "bad", "food" ] N = len(arr) countStringPairs(arr, N)# This code is contributed by mohit kumar 29 |
Javascript
<script>// Javascript program for the above approach// Function to count newly created pairs// by swapping the first characters of// any pairs of stringsfunction countStringPairs(a, n){ // Stores the count all possible // pair of strings let ans = 0; // Push all the strings // into the Unordered Map let s = new Map(); for(let i = 0; i < n; i++) { if(!s.has(a[i])) s.set(a[i],0); s.set(a[i], s.get(a[i]) + 1); } // Generate all possible pairs of // strings from the array arr[] for(let i = 0; i < n; i++) { for(let j = i + 1; j < n; j++) { // Store the current // pair of strings let p = (a[i]).split(""); let q = (a[j]).split(""); // Swap the first character if (p[0] != q[0]) { let t = p[0]; p[0] = q[0]; q[0] = t; // Check if both string // are not present in map if (!s.has(p.join("")) && !s.has(q.join(""))) { ans++; } } } } // Print the result document.write(ans);}// Driver codelet arr=["good", "bad", "food"];let N = arr.length;countStringPairs(arr, N);// This code is contributed by avanitrachhadiya2155</script> |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to count newly created pairs// by swapping the first characters of// any pairs of stringsstatic void countStringPairs(string[] a, int n){ // Stores the count all possible // pair of strings int ans = 0; // Push all the strings // into the Unordered Map Dictionary<string,int> s = new Dictionary<string,int>(); for(int i = 0; i < n; i++) { if(!s.ContainsKey(a[i])) s.Add(a[i],0); s[a[i]]++; } // Generate all possible pairs of // strings from the array arr[] for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // Store the current // pair of strings char[] p = (a[i]).ToCharArray(); char[] q = (a[j]).ToCharArray(); // Swap the first character if (p[0] != q[0]) { char t = p[0]; p[0]=q[0]; q[0]=t; // Check if both string // are not present in map if (!s.ContainsKey(new string(p)) && !s.ContainsKey(new string(q))) { ans++; } } } } // Print the result Console.WriteLine(ans);} // Driver code static public void Main () { string[] arr = {"good", "bad", "food"}; int N = arr.Length; countStringPairs(arr, N); }}// This code is contributed by rag2127. |
Output:
2
Time Complexity: O(N2)
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!
