Given an array, arr[] consisting of N strings where each character of the string is lower case English alphabet, the task is to store and print the occurrence of every distinct character in every string.
Examples:
Input: arr[] = { “neveropen”, “gfg” }
Output: Occurrences of: e = [1 2] [1 3] [1 10] [1 11]
Occurrences of: f = [1 6] [2 2]
Occurrences of: g = [1 1] [1 9] [2 1] [2 3]
Occurrences of: k = [1 4] [1 12]
Occurrences of: o = [1 7]
Occurrences of: r = [1 8]
Occurrences of: s = [1 5] [1 13]Input: arr[] = { “abc”, “ab” }
Output: Occurrences of: a = [1 1] [2 1]
Occurrences of: b = [1 2] [2 2]
Occurrences of: c = [1 3]
Approach: The above problem can be solved using Map and Vector data structures. Follow the steps below to solve the problem:
- Initialize a map<char, vector<pair<int, int>> > say mp to store the occurrences of a character in the vector of pairs, where each pair stores the index of the string in array as the first element and the position of the character in the string as the second element.
- Traverse the vector arr using a variable i and perform the following step:
- Iterate over the characters of the string arr[i] using variable j and in each iteration push the pair {i+1, j+1} in the vector mp[arr[i][j]].
- Finally, after completing the above steps, print the occurrences of every character by iterating over the map mp.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print every occurrence// of every characters in every stringvoid printOccurrences(vector<string> arr, int N){ map<char, vector<pair<int, int> > > mp; // Iterate over the vector arr[] for (int i = 0; i < N; i++) { // Traverse the string arr[i] for (int j = 0; j < arr[i].length(); j++) { // Push the pair of{i+1, j+1} // in mp[arr[i][j]] mp[arr[i][j]].push_back( make_pair(i + 1, j + 1)); } } // Print the occurrences of every // character for (auto it : mp) { cout << "Occurrences of: " << it.first << " = "; for (int j = 0; j < (it.second).size(); j++) { cout << "[" << (it.second)[j].first << " " << (it.second)[j].second << "] "; } cout << endl; }}// Driver Codeint main(){ // Input vector<string> arr = { "neveropen", "gfg" }; int N = arr.size(); // Function call printOccurrences(arr, N);} |
Java
import java.util.*;import java.util.Map.Entry;class GFG { public static void printOccurrences(List<String> arr, int N) { Map<Character, List<Pair<Integer, Integer>>> mp = new HashMap<>(); // Iterate over the List arr[] for (int i = 0; i < N; i++) { // Traverse the string arr[i] for (int j = 0; j < arr.get(i).length(); j++) { // Push the pair of{i+1, j+1} // in mp[arr[i][j]] if (!mp.containsKey(arr.get(i).charAt(j))) { mp.put(arr.get(i).charAt(j), new ArrayList<>()); } mp.get(arr.get(i).charAt(j)).add(new Pair<>(i + 1, j + 1)); } } // Print the occurrences of every // character for (Entry<Character, List<Pair<Integer, Integer>>> it : mp.entrySet()) { System.out.print("Occurrences of: " + it.getKey() + " = "); for (int j = 0; j < it.getValue().size(); j++) { System.out.print("[" + it.getValue().get(j).getKey() + " " + it.getValue().get(j).getValue() + "] "); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Input List<String> arr = Arrays.asList("neveropen", "gfg"); int N = arr.size(); // Function call printOccurrences(arr, N); }}// custom pair classclass Pair<T, U> { private T key; private U value; public Pair(T key, U value) { this.key = key; this.value = value; } public T getKey() { return key; } public U getValue() { return value; }}// This code is contributed by aadityapburujwale |
Python3
# Python3 program for the above approach# Function to print every occurrence# of every characters in every stringdef printOccurrences(arr, N): mp = [[] for i in range(26)] # Iterate over the vector arr[] for i in range(N): # Traverse the string arr[i] for j in range(len(arr[i])): # Push the pair of{i+1, j+1} # in mp[arr[i][j]] mp[ord(arr[i][j]) - ord('a')].append( (i + 1, j + 1)) # print(mp) # Print the occurrences of every # character for i in range(26): if len(mp[i]) == 0: continue print("Occurrences of:", chr(i + ord('a')), "=", end = " ") for j in mp[i]: print("[" + str(j[0]) + " " + str(j[1]) + "] ", end = "") print()# Driver Codeif __name__ == '__main__': # Input arr= [ "neveropen", "gfg" ] N = len(arr) # Function call printOccurrences(arr, N)# This code is contributed by mohit kumar 29 |
C#
using System;using System.Collections.Generic;class Program{ static void Main(string[] args) { string[] arr = { "neveropen", "gfg" }; int N = arr.Length; Dictionary<char, List<Tuple<int, int>>> mp = new Dictionary<char, List<Tuple<int, int>>>(); // Push the pair of{i+1, j+1} // in mp[arr[i][j]] for (int i = 0; i < N; i++) { for (int j = 0; j < arr[i].Length; j++) { if (!mp.ContainsKey(arr[i][j])) { mp[arr[i][j]] = new List<Tuple<int, int>>(); } mp[arr[i][j]].Add(Tuple.Create(i + 1, j + 1)); } } // Print the occurrences of every // character foreach (var item in mp) { Console.WriteLine("Occurrences of: " + item.Key + " = "); foreach (var pair in item.Value) { Console.Write("[" + pair.Item1 + " " + pair.Item2 + "] "); } Console.WriteLine(); } }}// This code is contributed by divyansh2212 |
Javascript
<script>// JavaScript program for the above approach// Function to print every occurrence// of every characters in every stringfunction printOccurrences(arr, N) { let mp = new Map(); // Iterate over the vector arr[] for (let i = 0; i < N; i++) { // Traverse the string arr[i] for (let j = 0; j < arr[i].length; j++) { // Push the pair of{i+1, j+1} // in mp[arr[i][j]] if (mp.has(arr[i][j])) { let temp = mp.get(arr[i][j]); temp.push([i + 1, j + 1]); mp.set(arr[i][j], temp); } else { mp.set(arr[i][j], [[i + 1, j + 1]]); } } } // Print the occurrences of every // character for (let it of new Map([...mp.entries()].sort())) { document.write("Occurrences of: " + it[0] + " = "); for (let j = 0; j < it[1].length; j++) { document.write(" [" + it[1][j][0] + " " + it[1][j][1] + "] "); } document.write("<br>"); }}// Driver Code// Inputlet arr = ["neveropen", "gfg"];let N = arr.length;// Function callprintOccurrences(arr, N);</script> |
Output
Occurrences of: e = [1 2] [1 3] [1 10] [1 11] Occurrences of: f = [1 6] [2 2] Occurrences of: g = [1 1] [1 9] [2 1] [2 3] Occurrences of: k = [1 4] [1 12] Occurrences of: o = [1 7] Occurrences of: r = [1 8] Occurrences of: s = [1 5] [1 13]
Time Complexity: O(N*M), where M is the length of the longest string.
Auxiliary Space: O(N*M)
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!
