Given two strings, we need to take the character which has the maximum occurrence in the first string, and then we have to check if that particular character is present in the second string the same number of times as it is present in the first string.
Examples:
Input : s1 = "sssgeek", s2 = "neveropenss"
Output : Yes
Max occurring character in s1 is
's'. It occurs same number of times
in s2.
Input : geekyarticle
gfggfggfg
Output : No
Store counts of characters in the first string and finds the maximum count. Now traverse through the second string and check if the maximum occurring character occurs the same number of times or not.
Algorithm:
- Create an array count of size 256 to keep the count of individual characters and initialize the array as 0.
- Iterate through the first string s1 and for each character, increment the count of that character in the count array.
- Find the maximum occurring character and its count in the count array using a loop:
a. Initialize variables mx_cnt and mx_chr to 0 and NULL character, respectively.
b. Iterate through the count array and for each character, if its count is greater than mx_cnt, update mx_cnt and mx_chr to the count and the character, respectively. - Iterate through the second string s2 and for each character, if it matches mx_chr, decrement mx_cnt.
- If mx_cnt is 0, return 1 to indicate that the maximum occurring character in the first string is present in the second string the same number of times as it occurs in the first string.
- If mx_cnt is not 0, return 0 to indicate that the condition is not met.
Below program to illustrate the above problem
C++
// C++ program to check the problem#include <bits/stdc++.h>using namespace std;#define ll long long#define ASCIISIZE 256int match(string s1, string s2){ // Create array to keep the count of individual // characters and initialize the array as 0 int count[ASCIISIZE] = { 0 }; // Construct character count array from the input // string. for (int i = 0; i < s1.length(); i++) count[s1[i]]++; // Count occurrences of maximum occurring character int mx_cnt = 0, mx_chr; for (int i = 0; i < ASCIISIZE; i++) { if (count[i] > mx_cnt) { mx_cnt = count[i]; mx_chr = i; } } // look if that character is present, the same // number of times it is present in second string for (int i = 0; i < s2.length(); i++) if (mx_chr == s2[i]) mx_cnt--; // check if sum is greater or equal to number // return 1 if (mx_cnt == 0) return 1;}// Driver program to test the above functionint main(){ string s1 = "geekforneveropen", s2 = "geekisgeeky"; if (match(s1, s2)) cout << "Yes "; else cout << "No"; return 0;} |
Java
// Java program to check the problemimport java.io.*;public class GFG {static int ASCIISIZE = 256;static int match(String s1, String s2){// Create array to keep the // count of individual characters // and initialize the array as 0int count[] = new int[ASCIISIZE];// Construct character count // array from the input string.char []s3 = s1.toCharArray();for (int i = 0; i < s3.length; i++) count[s3[i]]++;// Count occurrences of // maximum occurring characterint mx_cnt = 0;int mx_chr = 0;for (int i = 0; i < ASCIISIZE; i++) { if (count[i] > mx_cnt) { mx_cnt = count[i]; mx_chr = i; }}// look if that character is // present, the same number // of times it is present in// second stringchar []s4 = s2.toCharArray();for (int i = 0; i < s4.length; i++) if (mx_chr == s4[i]) mx_cnt--;// check if sum is greater or // equal to number return 1if (mx_cnt == 0) return 1;else return 0;}// Driver Codepublic static void main(String[] args) { String s1 = "geekforneveropen", s2 = "geekisgeeky"; int p = match(s1, s2); if (p == 1) System.out.println("Yes "); else System.out.println("No");}}// This code is contributed// by ChitraNayal |
Python3
# Python3 program to # check the problem# define function for Check # if max occurring character # of one string appears same# no. of times in otherdef match(s1, s2) : # declare empty list count_list = [] # iterate through each # character of the string for char in s1 : # find occurrence of # the character count = s1.count(char) # append tuple value # to the list count_list.append((count,char)) # return tuple of max count max_occ = max(count_list) # store max count in mx_cnt mx_cnt = max_occ[0] # store max count # character in mx_chr mx_chr = max_occ[1] # look if max count character # is present in s1, the same # number of times it is present # in second string s2 or not # if present return True # otherwise False. if mx_cnt == s2.count(mx_chr) : return True else : return False# Driver Codeif __name__ == "__main__" : s1 = "neveropen" s2 = "geekisgeeky" if match(s1,s2) : print("Yes") else : print("No") # This code is contributed# by Ankit Rai |
C#
// C# program to check the problemusing System;class GFG{static int ASCIISIZE = 256;static int match(String s1, String s2){// Create array to keep the // count of individual characters// and initialize the array as 0int []count = new int[ASCIISIZE];// Construct character count // array from the input string.for (int i = 0; i < s1.Length; i++) count[s1[i]]++;// Count occurrences of // maximum occurring characterint mx_cnt = 0;int mx_chr = 0;for (int i = 0; i < ASCIISIZE; i++) { if (count[i] > mx_cnt) { mx_cnt = count[i]; mx_chr = i; }}// look if that character is // present, the same number// of times it is present // in second stringfor (int i = 0; i < s2.Length; i++) if (mx_chr == s2[i]) mx_cnt--;// check if sum is greater// or equal to number return 1if (mx_cnt == 0) return 1;else return 0;}// Driver Codepublic static void Main(){ String s1 = "geekforneveropen", s2 = "geekisgeeky"; int p = match(s1, s2); if (p == 1) Console.Write("Yes "); else Console.Write("No");}}// This code is contributed// by ChitraNayal |
Javascript
<script>// Javascript program to check the problem let ASCIISIZE = 256;function match(s1,s2){ // Create array to keep the // count of individual characters // and initialize the array as 0let count = new Array(ASCIISIZE);for(let i=0;i<ASCIISIZE;i++){ count[i]=0;}// Construct character count // array from the input string.let s3 = s1.split("");for (let i = 0; i < s3.length; i++) count[s3[i]]++; // Count occurrences of // maximum occurring characterlet mx_cnt = 0;let mx_chr = 0;for (let i = 0; i < ASCIISIZE; i++) { if (count[i] > mx_cnt) { mx_cnt = count[i]; mx_chr = i; }} // look if that character is // present, the same number // of times it is present in// second stringlet s4 = s2.split("");for (let i = 0; i < s4.length; i++) if (mx_chr == s4[i]) mx_cnt--; // check if sum is greater or // equal to number return 1if (mx_cnt == 0) return 1;else return 0;}// Driver Codelet s1 = "geekforneveropen", s2 = "geekisgeeky";let p = match(s1, s2);if (p == 1) document.write("Yes ");else document.write("No"); // This code is contributed by avanitrachhadiya2155</script> |
Output:
Yes
Time Complexity: O(m + n), where m is the size of string s1 and n is the size of string s2.
Auxiliary Space: O(256), no extra space required, so it is a constant.
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!
