Given an array of strings arr[], the task is to print all unique strings that are present in the given array.
Examples:
Input: arr[] = { “neveropen”, “geek”, “ab”, “geek” “code”, “karega” }
Output: neveropen ab code karega
Explanation:
The frequency of the string “neveropen” is 1.
The frequency of the string “geek” is 2.
The frequency of the string “ab” is 1.
The frequency of the string “code” is 1.
The frequency of the string “karega” is 1.
Therefore, the required output is “neveropen ab code karega”Input: arr[] = { “abcde”, “abcd”, “abcd”, “co” “”, “code” }
Output: abcde co code
Naive Approach: The simplest approach to solve this problem is to traverse the array for every string encountered, check if that string occurs in the remaining array or not. Print those strings which are occurring only once in the array.
Time Complexity: O(N2 * M), where M is the maximum length of the string
Auxiliary Space: O(1)
Efficient Approach using STL:
Another approach to print all the unique elements in array is by using unordered_map.
Steps involved in this approach are as follows:
- In first step an unordered_map(freqMap) is declared, which will be used to store the frequency of each string in the array.
- Then we run a for loop for all the elements of the array. In each iteration, the frequency of the i-th string in the array is incremented in the map.
- Then we iterate through this unordered_map and print all the strings which is present only one time in the array.
Below is the code for the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to Print all Unique Strings // present in a given Arrayvoid printUniqueStrings(vector<string> arr) { unordered_map<string, int> freqMap; // Count the frequency of each string in arr for (auto str : arr) { ++freqMap[str]; } // Print unique strings in arr for (auto p : freqMap) { if (p.second == 1) { std::cout << p.first << " "; } }}int main() { vector<string> arr = {"neveropen", "for", "geek", "ab", "geek", "for", "code", "karega"}; printUniqueStrings(arr); return 0;}// This code is contributed by Vaibhav |
Java
// Java codeimport java.util.*;public class Main { // Function to Print all Unique Strings // present in a given Array static void printUniqueStrings(String[] arr) { Map<String, Integer> freqMap = new HashMap<>(); // Count the frequency of each string in arr for (String str : arr) { freqMap.put(str, freqMap.getOrDefault(str, 0) + 1); } // Print unique strings in arr for (Map.Entry<String, Integer> entry : freqMap.entrySet()) { if (entry.getValue() == 1) { System.out.print(entry.getKey() + " "); } } } public static void main(String[] args) { String[] arr = {"neveropen", "for", "geek", "ab", "geek", "for", "code", "karega"}; printUniqueStrings(arr); }} |
Python3
# Function to Print all Unique Strings # present in a given Arraydef printUniqueStrings(arr): freqMap = {} # Count the frequency of each string in arr for str in arr: freqMap[str] = freqMap.get(str, 0) + 1 # Print unique strings in arr for key, value in freqMap.items(): if value == 1: print(key, end=" ")arr = ["neveropen", "for", "geek", "ab", "geek", "for", "code", "karega"]printUniqueStrings(arr) |
C#
using System;using System.Collections.Generic;class MainClass { // Function to Print all Unique Strings // present in a given Array static void printUniqueStrings(string[] arr) { Dictionary<string, int> freqMap = new Dictionary<string, int>(); // Count the frequency of each string in arr foreach (string str in arr) { freqMap[str] = freqMap.GetValueOrDefault(str, 0) + 1; } // Print unique strings in arr foreach (KeyValuePair<string, int> entry in freqMap) { if (entry.Value == 1) { Console.Write(entry.Key + " "); } } } public static void Main(string[] args) { string[] arr = {"neveropen", "for", "geek", "ab", "geek", "for", "code", "karega"}; printUniqueStrings(arr); }} |
Javascript
function printUniqueStrings(arr) { let freqMap = {}; // Count the frequency of each string in arr for (let str of arr) { freqMap[str] = (freqMap[str] || 0) + 1; } // Print unique strings in arr for (let [key, value] of Object.entries(freqMap)) { if (value === 1) { console.log(key + " "); } }}let arr = ["neveropen", "for", "geek", "ab", "geek", "for", "code", "karega"];printUniqueStrings(arr); |
Output
karega code ab neveropen
Time Complexity: O(N*M) where N is the number of strings in the array and M is the maximum length of the strings.
Space Complexity: O(N*M)
Efficient Approach: The above approach can be optimized using Trie. The idea is to traverse the array and for every ith string in the array, check if arr[i] is present in the Trie or not. If found to be true, then mark arr[i] as duplicate array element. Otherwise, mark arr[i] as unique array element and insert arr[i] into the trie. Follow the steps below to solve the problem:
- Initialize an array, say isUniq[], to check if an array element is unique or not.
- Create a Trie having a root node, say root, to store the characters of each string present in the given array.
- Traverse the array using variable i and for every ith element, check if arr[i] is present in the Trie or not. IF found to be true, then update isUniq[i] to false.
- Otherwise, update isUniq[i] to true and insert arr[i] into the Trie.
- Finally, traverse the isUniq[] array using variable i and for every ith element, check if isUniq[i] is true or not. If found to be true, then print arr[i].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of// a Trie nodestruct TrieNode { // Stores index // of string int idx; // Check if a character is // present in the string or not TrieNode* child[26]; // Initialize a TrieNode TrieNode() { // Idx = -1: String is not // present in TrieNode idx = -1; // Initialize all child nodes // of a TrieNode to NULL for (int i = 0; i < 26; i++) { // Update child[i] child[i] = NULL; } }};// Function to insert a string into Trievoid Insert(TrieNode* root, string str, int i){ // Stores length of the string int N = str.length(); // Traverse the string str for (int i = 0; i < N; i++) { // If str[i] not present in // a Trie at current index if (!root->child[str[i] - 'a']) { // Create a new node of Trie. root->child[str[i] - 'a'] = new TrieNode(); } // Update root root = root->child[str[i] - 'a']; } // Store index of str // in the TrieNode root->idx = i;}// Function to check if string str present// in the Trie or notint SearchString(TrieNode* root, string str){ // Stores length of // the string int N = str.length(); // Traverse the string for (int i = 0; i < N; i++) { // If a character not present // in Trie at current index if (!root->child[str[i] - 'a']) { // Return str as // unique string return -1; } // Update root root = root->child[str[i] - 'a']; } // Return index of str return root->idx;}// Utility function to find the unique// string in array of stringsvoid UtilUniqStr(vector<string>& arr, int N){ // Stores root node of the Trie TrieNode* root = new TrieNode(); // isUniq[i]: Check if i-th string // is unique or not bool isUniq[N]; // Initialize isUniq[] to false memset(isUniq, false, sizeof(isUniq)); // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique string isUniq[0] = true; // Traverse the given array for (int i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array int idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th string // as unique string isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th string as // duplicate string in Trie isUniq[idx] = false; } } // Traverse the array for (int i = 0; i < N; i++) { // If i-th string is unique, // then print the string if (isUniq[i]) { cout << arr[i] << " "; } }}// Driver Codeint main(){ vector<string> arr = { "neveropen", "for", "geek", "ab", "geek", "for", "code", "karega" }; int N = arr.size(); UtilUniqStr(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;public class GFG{// Structure of// a Trie nodestatic class TrieNode { // Stores index // of String int idx; // Check if a character is // present in the String or not TrieNode []child = new TrieNode[26]; // Initialize a TrieNode TrieNode() { // Idx = -1: String is not // present in TrieNode idx = -1; // Initialize all child nodes // of a TrieNode to null for (int i = 0; i < 26; i++) { // Update child[i] child[i] = null; } }};// Function to insert a String into Triestatic void Insert(TrieNode root, String str, int i){ // Stores length of the String int N = str.length(); // Traverse the String str for (int j = 0; j < N; j++) { // If str[i] not present in // a Trie at current index if (root.child[str.charAt(j) - 'a']==null) { // Create a new node of Trie. root.child[str.charAt(j) - 'a'] = new TrieNode(); } // Update root root = root.child[str.charAt(j) - 'a']; } // Store index of str // in the TrieNode root.idx = i;}// Function to check if String str present// in the Trie or notstatic int SearchString(TrieNode root, String str){ // Stores length of // the String int N = str.length(); // Traverse the String for (int i = 0; i < N; i++) { // If a character not present // in Trie at current index if (root.child[str.charAt(i) - 'a'] == null) { // Return str as // unique String return -1; } // Update root root = root.child[str.charAt(i) - 'a']; } // Return index of str return root.idx;}// Utility function to find the unique// String in array of Stringsstatic void UtilUniqStr(String[] arr, int N){ // Stores root node of the Trie TrieNode root = new TrieNode(); // isUniq[i]: Check if i-th String // is unique or not boolean []isUniq = new boolean[N]; // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique String isUniq[0] = true; // Traverse the given array for (int i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array int idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th String // as unique String isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th String as // duplicate String in Trie isUniq[idx] = false; } } // Traverse the array for (int i = 0; i < N; i++) { // If i-th String is unique, // then print the String if (isUniq[i]) { System.out.print(arr[i]+ " "); } }}// Driver Codepublic static void main(String[] args){ String[] arr = { "neveropen", "for", "geek", "ab", "geek", "for", "code", "karega" }; int N = arr.length; UtilUniqStr(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approachroot = None# Structure of# a Trie nodeclass TrieNode: # Stores index # of string def __init__(self): self.idx = -1 self.child = [None]*26# Function to insert a string into Triedef Insert(str, i): global root # Stores length of the string N = len(str) root1 = root # Traverse the string str for i in range(N): # If str[i] not present in # a Trie at current index if (not root1.child[ord(str[i]) - ord('a')]): # Create a new node of Trie. root1.child[ord(str[i]) - ord('a')] = TrieNode() # Update root root1 = root1.child[ord(str[i]) - ord('a')] # Store index of str # in the TrieNode root1.idx = i return root1# Function to check if string str present# in the Trie or notdef SearchString(str): global root root1 = root # Stores length of # the N = len(str) # Traverse the for i in range(N): # If a character not present # in Trie at current index if (not root1.child[ord(str[i]) - ord('a')]): # Return str as # unique return -1 # Update root root1 = root1.child[ord(str[i]) - ord('a')] # Return index of str return root1.idx# Utility function to find the unique# string in array of stringsdef UtilUniqStr(arr, N): global root # Stores root node of the Trie root = TrieNode() d = {} for i in arr: d[i] = d.get(i, 0) + 1 # isUniq[i]: Check if i-th string # is unique or not isUniq = [False] * N # Initialize isUniq[] to false # memset(isUniq, false, sizeof(isUniq)); # Insert arr[0] into the Trie Insert(arr[0], 0) # Mark arr[0] as unique string isUniq[0] = True # print(root.child[6].child) # Traverse the given array for i in range(1, N): # Stores previous 1st index # of arr[i] in the array idx = SearchString(arr[i]) # If arr[i] not present # in the Trie if (idx == -1 and d[arr[i]] == 1): # Mark i-th string # as unique string isUniq[i] = True # Insert arr[i] into Trie Insert(arr[i], i) # If arr[i] already present # in the Trie else: # Mark i-th string as # duplicate string in Trie isUniq[idx] = False # Traverse the array for i in range(N): # If i-th string is unique, # then print the string if (isUniq[i]): print(arr[i], end = " ")# Driver Codeif __name__ == '__main__': arr = ["neveropen", "for","geek", "ab", "geek","for", "code", "karega"] N = len(arr) UtilUniqStr(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{// Structure of// a Trie nodeclass TrieNode { // Stores index // of String public int idx; // Check if a character is // present in the String or not public TrieNode []child = new TrieNode[26]; // Initialize a TrieNode public TrieNode() { // Idx = -1: String is not // present in TrieNode idx = -1; // Initialize all child nodes // of a TrieNode to null for (int i = 0; i < 26; i++) { // Update child[i] child[i] = null; } }};// Function to insert a String into Triestatic void Insert(TrieNode root, String str, int i){ // Stores length of the String int N = str.Length; // Traverse the String str for (int j = 0; j < N; j++) { // If str[i] not present in // a Trie at current index if (root.child[str[j] - 'a'] == null) { // Create a new node of Trie. root.child[str[j] - 'a'] = new TrieNode(); } // Update root root = root.child[str[j] - 'a']; } // Store index of str // in the TrieNode root.idx = i;}// Function to check if String str present// in the Trie or notstatic int SearchString(TrieNode root, String str){ // Stores length of // the String int N = str.Length; // Traverse the String for (int i = 0; i < N; i++) { // If a character not present // in Trie at current index if (root.child[str[i] - 'a'] == null) { // Return str as // unique String return -1; } // Update root root = root.child[str[i] - 'a']; } // Return index of str return root.idx;}// Utility function to find the unique// String in array of Stringsstatic void UtilUniqStr(String[] arr, int N){ // Stores root node of the Trie TrieNode root = new TrieNode(); // isUniq[i]: Check if i-th String // is unique or not bool []isUniq = new bool[N]; // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique String isUniq[0] = true; // Traverse the given array for (int i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array int idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th String // as unique String isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th String as // duplicate String in Trie isUniq[idx] = false; } } // Traverse the array for (int i = 0; i < N; i++) { // If i-th String is unique, // then print the String if (isUniq[i]) { Console.Write(arr[i] + " "); } }}// Driver Codepublic static void Main(String[] args){ String[] arr = { "neveropen", "for", "geek", "ab", "geek", "for", "code", "karega" }; int N = arr.Length; UtilUniqStr(arr, N);}} // This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approach// Structure of// a Trie nodeclass TrieNode{ constructor() { this.idx = -1; this.child = new Array(26); for (let i = 0; i < 26; i++) { // Update child[i] this.child[i] = null; } }}// Function to insert a String into Triefunction Insert(root,str,i){ // Stores length of the String let N = str.length; // Traverse the String str for (let j = 0; j < N; j++) { // If str[i] not present in // a Trie at current index if (root.child[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]==null) { // Create a new node of Trie. root.child[str[j].charCodeAt(0) - 'a'.charCodeAt(0)] = new TrieNode(); } // Update root root = root.child[str[j].charCodeAt(0) - 'a'.charCodeAt(0)]; } // Store index of str // in the TrieNode root.idx = i;}// Function to check if String str present// in the Trie or notfunction SearchString(root,str){ // Stores length of // the String let N = str.length; // Traverse the String for (let i = 0; i < N; i++) { // If a character not present // in Trie at current index if (root.child[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] == null) { // Return str as // unique String return -1; } // Update root root = root.child[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]; } // Return index of str return root.idx;}// Utility function to find the unique// String in array of Stringsfunction UtilUniqStr(arr,N){ // Stores root node of the Trie let root = new TrieNode(); // isUniq[i]: Check if i-th String // is unique or not let isUniq = new Array(N); // Insert arr[0] into the Trie Insert(root, arr[0], 0); // Mark arr[0] as unique String isUniq[0] = true; // Traverse the given array for (let i = 1; i < N; i++) { // Stores previous 1st index // of arr[i] in the array let idx = SearchString(root, arr[i]); // If arr[i] not present // in the Trie if (idx == -1) { // Mark i-th String // as unique String isUniq[i] = true; // Insert arr[i] into Trie Insert(root, arr[i], i); } // If arr[i] already present // in the Trie else { // Mark i-th String as // duplicate String in Trie isUniq[idx] = false; } } // Traverse the array for (let i = 0; i < N; i++) { // If i-th String is unique, // then print the String if (isUniq[i]) { document.write(arr[i]+ " "); } }}// Driver Codelet arr=["neveropen", "for", "geek", "ab", "geek", "for", "code", "karega" ];let N = arr.length; UtilUniqStr(arr, N);// This code is contributed by patel2127</script> |
Output
neveropen ab code karega
Time Complexity: O(N * M), where M is the maximum length of the string
Auxiliary Space: O(N * 26)
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!
