Given a string str and an array of strings arr[] of size N, the task is to print a string from arr[], which has maximum count of matching characters with str.
Examples:
Input: str = “vikas”, N = 3, arr[] = [“preeti”, “khusbu”, “katherina”]
Output: “katherina”
Explanation:
Number of similar characters between Str and each string in D[ ] are,
“preeti” = 1
“khusbu” = 2
“katherina” = 3
Hence, “katherina” has maximum matching characters.Input: str = “gfg”, N = 3, arr[] = [“goal”, “fog”, “abc”]
Output: “fog”
Explanation:
Number of similar characters between Str and each string in D[ ] are,
“goal” = 1
“fog” = 2
“abc” = 0
Hence, “fog” has maximum matching characters.
Approach: The idea is to consider each string of array arr[], and compare each of its character with the given string str. Keep track of the maximum number of matching characters and corresponding string. Also, make sure to remove the duplicates from each string. Below are the steps:
- Create a variable maxVal and a variable val, to keep track of maximum number of matching characters and corresponding string respectively.
- Traverse the array arr[] and remove duplicates from each string. Also, remove duplicates from Str.
- For each string of arr[], compare it with the given string str, and count the number of matching characters.
- Keep updating maxVal with the maximum number of matching characters and val with corresponding string.
- Finally, print the value of val after the above operations.
Below is the implementation of the above approach:
Java
// Java program for the above approachimport java.util.*;import java.io.*;public class GFG { // Function that print string which // has maximum similar characters private static void maxMatchingChar(ArrayList<String> list, int n, char ch[]) { String val = ""; int maxVal = Integer.MIN_VALUE; for (String s : list) { // Count matching characters int matchingchar = matchingChar( s.toLowerCase(), ch); // Update maxVal if needed if (matchingchar > maxVal) { maxVal = matchingchar; val = s; } } System.out.print(val + " "); } // Function that returns the count // of number of matching characters private static int matchingChar( String s, char[] ch) { int freq = 0, c = ch.length; // Traverse the character array for (int i = 0; i < c; i++) { // If character matches // then increment the count if (s.contains( String.valueOf(ch[i]))) { freq++; } } return freq; } // Function to remove duplicate // characters private static char[] removeDuplicate(String str) { // To keep unique character only HashSet<Character> set = new HashSet<Character>(); int c = str.length(); // Inserting character in hashset for (int i = 0; i < c; i++) { set.add(str.charAt(i)); } char arr[] = new char[set.size()]; int index = 0; // Update string with unique characters for (char s : set) { arr[index] = s; index++; } // Return the char array return arr; } // Driver Code public static void main( String[] args) throws Exception { int n = 3; String str = "Vikas"; String D[] = { "preeti", "khusbu", "katherina" }; // Removing duplicate and // convert to lowercase char ch[] = removeDuplicate(str.toLowerCase()); ArrayList<String> list = new ArrayList<String>(); // Insert each string in the list for (int i = 0; i < n; i++) { list.add(D[i]); } // Function Call maxMatchingChar(list, n, ch); }} |
Python3
# Python3 program for the above approachimport sys# Function that print string which # has maximum similar charactersdef maxMatchingChar(list, n, ch): val = "" maxVal = -sys.maxsize - 1 for s in list: # Count matching characters matchingchar = matchingChar(s.lower(), ch) # Update maxVal if needed if (matchingchar > maxVal): maxVal = matchingchar val = s print(val, end = " ")# Function that returns the count # of number of matching charactersdef matchingChar(s, ch): freq = 0 c = len(ch) # Traverse the character array for i in range(c): # If character matches # then increment the count if ch[i] in s: freq += 1 return freq# Driver Code n = 3str = "Vikas"D = [ "preeti", "khusbu", "katherina" ]# Remove duplicate characters and# convert to lowercase ch = list(set(str.lower()))List = []# Insert each string in the listfor i in range(n): List.append(D[i])# Function call maxMatchingChar(List, n, ch)# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function that print string which// has maximum similar charactersprivate static void maxMatchingChar(List<String> list, int n, char []ch){ String val = ""; int maxVal = int.MinValue; foreach(String s in list) { // Count matching characters int matchingchar = matchingChar( s.ToLower(), ch); // Update maxVal if needed if (matchingchar > maxVal) { maxVal = matchingchar; val = s; } } Console.Write(val + " ");}// Function that returns the count// of number of matching charactersprivate static int matchingChar(String s, char[] ch){ int freq = 0, c = ch.Length; // Traverse the character array for(int i = 0; i < c; i++) { // If character matches // then increment the count if (s.Contains(String.Join("", ch[i]))) { freq++; } } return freq;}// Function to remove duplicate// charactersprivate static char[] removeDuplicate(String str){ // To keep unique character only HashSet<char> set = new HashSet<char>(); int c = str.Length; // Inserting character in hashset for(int i = 0; i < c; i++) { set.Add(str[i]); } char []arr = new char[set.Count]; int index = 0; // Update string with unique characters foreach(char s in set) { arr[index] = s; index++; } // Return the char array return arr;}// Driver Codepublic static void Main(String[] args) { int n = 3; String str = "Vikas"; String []D = { "preeti", "khusbu", "katherina" }; // Removing duplicate and // convert to lowercase char []ch = removeDuplicate(str.ToLower()); List<String> list = new List<String>(); // Insert each string in the list for(int i = 0; i < n; i++) { list.Add(D[i]); } // Function call maxMatchingChar(list, n, ch);}}// This code is contributed by Rohit_ranjan |
C++
#include <bits/stdc++.h>using namespace std;// Function that returns the count// of number of matching charactersint matchingChar(string s, char ch[], int c) { int freq = 0; // Traverse the character array for (int i = 0; i < c; i++) { // If character matches // then increment the count if (s.find(ch[i]) != string::npos) { freq++; } } return freq;}// Function to remove duplicate// characterschar* removeDuplicate(string str) { // To keep unique character only unordered_set<char> set; int c = str.length(); // Inserting character in hashset for (int i = 0; i < c; i++) { set.insert(tolower(str[i])); } char *arr = new char[set.size()]; int index = 0; // Update string with unique characters for (char s : set) { arr[index] = s; index++; } // Return the char array return arr;}// Function that print string which// has maximum similar charactersvoid maxMatchingChar(vector<string> list, int n, char ch[], int c) { string val = ""; int maxVal = INT_MIN; for (string s : list) { // Count matching characters int matchingchar = matchingChar(s, ch, c); // Update maxVal if needed if (matchingchar > maxVal) { maxVal = matchingchar; val = s; } } cout << val << " ";}int main() { int n = 3; string str = "Vikas"; string D[] = { "preeti", "khusbu", "katherina" }; // Removing duplicate and // convert to lowercase char *ch = removeDuplicate(str); int c = strlen(ch); vector<string> list; // Insert each string in the list for (int i = 0; i < n; i++) { list.push_back(D[i]); } // Function Call maxMatchingChar(list, n, ch, c); return 0;} |
Javascript
function maxMatchingChar(list, n, ch) { let val = ""; let maxVal = -Number.MAX_SAFE_INTEGER; for (let i = 0; i < n; i++) { let s = list[i]; // Count matching characters let matchingchar = matchingChar(s.toLowerCase(), ch); // Update maxVal if needed if (matchingchar > maxVal) { maxVal = matchingchar; val = s; } } console.log(val + " ");}function matchingChar(s, ch) { let freq = 0; let c = ch.length; // Traverse the character array for (let i = 0; i < c; i++) { // If character matches then increment the count if (s.includes(ch[i])) { freq += 1; } } return freq;}// Driver Code let n = 3;let str = "Vikas";let D = [ "preeti", "khusbu", "katherina" ];// Remove duplicate characters and convert to lowercase let ch = Array.from(new Set(str.toLowerCase()));let list = [];// Insert each string in the listfor (let i = 0; i < n; i++) { list.push(D[i]);}// Function call maxMatchingChar(list, n, ch); |
Output:
katherina
Time Complexity: O(N*M) where M is the maximum length of a string.
Auxiliary space: O(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!