Given an array arr[] of strings and integers X and Y, the task is to find the count of strings with frequency of each character at most X and length of the string at least Y.
Examples:
Input: arr[] = { “ab”, “derdee”, “erre” }, X = 2, Y = 4
Output: 1
Explanation: Strings with character frequency at most 2 and
length at least 4 is “erre”. Hence count is 1Input: arr[] = {“ag”, “ka”, “nanana”}, X = 3, Y = 2
Output: 3
Approach: Follow the approach mentioned below to solve the problem:
- Traverse the array of string, and for each string follow the steps below.
- Create a frequency map of characters.
- Whenever any character has a frequency greater than X, or length less than Y, skip the current string.
- If no character has frequency more than X, and length at least Y, increment the count of answer.
- Return the count stored in answer when all the strings are traversed.
C++
#include <bits/stdc++.h>using namespace std;// Function to check if// the string has// frequency of each character// less than Xbool isValid(string s, int X){ vector<int> freq(26, 0); // Loop to check the frequency // of each character in the string for (char c : s) { freq++; } // Loop to check // if the frequency of all characters // are at most X for (int i = 0; i < 26; i++) if (freq[i] > X) return false; return true;}// Function to calculate the count of stringsint getCount(vector<string>& arr, int X, int Y){ int ans = 0; // Loop to iterate the string array for (string st : arr) { if (isValid(st, X) && st.length() >= Y) { ans++; } } return ans;}// Driver Codeint main(){ vector<string> arr = { "ab", "derdee", "erre" }; int X = 2, Y = 4; // Function call to get count for arr[] cout << getCount(arr, X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to check if // the string has // frequency of each character // less than X static boolean isValid(String s, int X) { int freq[] = new int[26]; // Loop to check the frequency // of each character in the string for (int i=0;i<s.length();i++) { char c = s.charAt(i); freq++; } // Loop to check // if the frequency of all characters // are at most X for (int i = 0; i < 26; i++) if (freq[i] > X) return false; return true; } // Function to calculate the count of strings static int getCount(String[] arr, int X, int Y) { int ans = 0; // Loop to iterate the string array for (String st : arr) { if (isValid(st, X) && st.length() >= Y) { ans++; } } return ans; } // Driver Code public static void main (String[] args) { String arr[] = { "ab", "derdee", "erre" }; int X = 2, Y = 4; // Function call to get count for arr[] System.out.println(getCount(arr, X, Y)); }}// This code is contributed by Potta Lokesh |
Python3
# Function to check if# the string has# frequency of each character# less than Xdef isValid (s, X) : freq = [0] * 26 # Loop to check the frequency # of each character in the string for c in s: freq[ord(c) - ord("a")] += 1 # Loop to check # if the frequency of all characters # are at most X for i in range(26): if (freq[i] > X): return False return True# Function to calculate the count of stringsdef getCount (arr, X, Y): ans = 0 # Loop to iterate the string array for st in arr: if (isValid(st, X) and len(st) >= Y): ans += 1 return ans# Driver Codearr = ["ab", "derdee", "erre"]X = 2Y = 4# Function call to get count for arr[]print(getCount(arr, X, Y))# This code is contributed by gfgking. |
C#
// C# program for the above approachusing System;class GFG{// Function to check if the string// has frequency of each character// less than Xstatic bool isValid(String s, int X){ int []freq = new int[26]; // Loop to check the frequency // of each character in the string for(int i = 0; i < s.Length; i++) { char c = s[i]; freq++; } // Loop to check if the frequency // of all characters are at most X for(int i = 0; i < 26; i++) if (freq[i] > X) return false; return true;}// Function to calculate the count of stringsstatic int getCount(String[] arr, int X, int Y){ int ans = 0; // Loop to iterate the string array foreach (String st in arr) { if (isValid(st, X) && st.Length >= Y) { ans++; } } return ans;}// Driver Codepublic static void Main(String[] args){ String []arr = { "ab", "derdee", "erre" }; int X = 2, Y = 4; // Function call to get count for []arr Console.WriteLine(getCount(arr, X, Y));}}// This code is contributed by shikhasingrajput |
Javascript
<script> // Function to check if // the string has // frequency of each character // less than X const isValid = (s, X) => { let freq = new Array(26).fill(0); // Loop to check the frequency // of each character in the string for (let c in s) { freq[s.charCodeAt(c) - "a".charCodeAt(0)]++; } // Loop to check // if the frequency of all characters // are at most X for (let i = 0; i < 26; i++) if (freq[i] > X) return false; return true; } // Function to calculate the count of strings const getCount = (arr, X, Y) => { let ans = 0; // Loop to iterate the string array for (let st in arr) { if (isValid(arr[st], X) && arr[st].length >= Y) { ans++; } } return ans; } // Driver Code let arr = ["ab", "derdee", "erre"]; let X = 2, Y = 4; // Function call to get count for arr[] document.write(getCount(arr, X, Y)); // This code is contributed by rakeshsahni</script> |
Output
1
Time Complexity: O(N*M), where N is the size of the array and M is the size of the longest string
Auxiliary Space: O(1)
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!
