Given a string S, the task is to find the prefix of string S with the maximum possible length such that frequency of each character in the prefix is at most the number of characters in S with minimum frequency.
Examples:
Input: S = ‘aabcdaab’
Output: aabcd
Explanation:
Frequency of characters in the given string –
{a: 4, b: 2, c: 1, d: 1}
Minimum frequency in 1 and the count of minimum frequency is 2,
So frequency of each character in the prefix can be at most 2.Input: S = ‘aaabc’
Output: aa
Explanation:
Frequency of characters in the given string –
{a: 3, b: 1, c: 1}
Minimum frequency in 1 and the count of minimum frequency is 2,
So frequency of each character in the prefix can be at most 2.
Approach:
- Initialize a hash-map to store the frequency of the characters.
- Iterate over the string and increment the frequency of the character in the hash-map.
- Find the minimum occurred character in the string and the count of such characters whose frequency is minimum.
- Initialize another hash-map to store the frequency of the characters of the possible prefix string.
- Finally, Iterate over the string from start and increment the count of the characters until the frequency of any characters is not greater than the count of the minimum frequency.
Below is the implementation of the above approach:
C++
// C++ implementation to find the prefix// of the s such that occurrence of each// character is atmost the count of minimum// frequency in the s#include <bits/stdc++.h>using namespace std;// Function to find the maximum// possible prefix of the svoid MaxPrefix(string s){ // Hash map to store the frequency // of the characters in the s map<char, int> Dict; // Iterate over the s to find // the occurrence of each Character for(char i : s) { Dict[i]++; } int minfrequency = INT_MAX; // Minimum frequency of the Characters for(auto x : Dict) { minfrequency = min(minfrequency, x.second); } int countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map for(auto x: Dict) { if (x.second == minfrequency) countminFrequency += 1; } map<char, int> mapper; int indi = 0; // Loop to find the maximum possible // length of the prefix in the s for(char i: s) { mapper[i] += 1; // Condition to check if the frequency // is greater than minimum possible freq if (mapper[i] > countminFrequency) break; indi += 1; } // maxprefix s and its length. cout << (s.substr(0, indi));}// Driver codeint main(){ // s is initialize. string str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str);}// This code is contributed by mohit kumar 29 |
Java
// Java implementation to find the prefix// of the s such that occurrence of each// character is atmost the count of minimum // frequency in the simport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Function to find the maximum// possible prefix of the sstatic void MaxPrefix(String s){ // Hash map to store the frequency // of the characters in the s Map<Character, Integer> Dict = new HashMap<>(); // Iterate over the s to find // the occurrence of each Character for(char i : s.toCharArray()) { Dict.put(i, Dict.getOrDefault(i, 0) + 1); } int minfrequency = Integer.MAX_VALUE; // Minimum frequency of the Characters for(Integer x: Dict.values()) { minfrequency = Math.min(minfrequency, x); } int countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map for(Map.Entry<Character, Integer> x: Dict.entrySet()) { if (x.getValue() == minfrequency) countminFrequency += 1; } Map<Character, Integer> mapper = new HashMap<>(); int indi = 0; // Loop to find the maximum possible // length of the prefix in the s for(char i: s.toCharArray()) { mapper.put(i, mapper.getOrDefault(i, 0) + 1); // Condition to check if the frequency // is greater than minimum possible freq if (mapper.get(i) > countminFrequency) break; indi += 1; } // maxprefix s and its length. System.out.println(s.substring(0, indi));}// Driver codepublic static void main(String[] args){ // s is initialize. String str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str); }}// This code is contributed by offbeat |
Python3
# Python3 implementation to find the# prefix of the string such that # occurrence of each character is# atmost the count of minimum # frequency in the string# Function to find the maximum# possible prefix of the stringdef MaxPrefix(string): # Hash map to store the frequency # of the characters in the string Dict = {} maxprefix = 0 # Iterate over the string to find # the occurrence of each Character for i in string: Dict[i] = Dict.get(i, 0) + 1 # Minimum frequency of the Characters minfrequency = min(Dict.values()) countminFrequency = 0 # Loop to find the count of minimum # frequency in the hash-map for x in Dict: if (Dict[x] == minfrequency): countminFrequency += 1 mapper = {} indi = 0 # Loop to find the maximum possible # length of the prefix in the string for i in string: mapper[i] = mapper.get(i, 0) + 1 # Condition to check if the frequency # is greater than minimum possible freq if (mapper[i] > countminFrequency): break indi += 1 # maxprefix string and its length. print(string[:indi])# Driver code if __name__ == '__main__': # String is initialize. str = 'aabcdaab' # str is passed in MaxPrefix function. MaxPrefix(str) |
C#
// C# implementation to find the// prefix of the s such that // occurrence of each character is// atmost the count of minimum // frequency in the susing System;using System.Collections;using System.Collections.Generic;using System.Linq;class GFG{ // Function to find the maximum// possible prefix of the sstatic void MaxPrefix(string s){ // Hash map to store the frequency // of the characters in the s Dictionary<char, int> Dict = new Dictionary<char, int>(); // Iterate over the s to find // the occurrence of each Character foreach(char i in s) { if (Dict.ContainsKey(i)) { Dict[i]++; } else { Dict[i] = 1; } } int minfrequency = Int32.MaxValue; // Minimum frequency of the Characters foreach(int x in Dict.Values.ToList()) { minfrequency = Math.Min(minfrequency, x); } int countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map foreach(char x in Dict.Keys.ToList()) { if (Dict[x] == minfrequency) countminFrequency += 1; } Dictionary<char, int> mapper = new Dictionary<char, int>(); int indi = 0; // Loop to find the maximum possible // length of the prefix in the s foreach(char i in s) { if (mapper.ContainsKey(i)) { mapper[i]++; } else { mapper[i] = 1; } // Condition to check if the frequency // is greater than minimum possible freq if (mapper[i] > countminFrequency) break; indi += 1; } // maxprefix s and its length. Console.Write(s.Substring(0, indi));}// Driver Codepublic static void Main(string[] args){ // s is initialize. string str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str);}}// This code is contributed by rutvik_56 |
Javascript
<script> // JavaScript implementation to find the // prefix of the s such that // occurrence of each character is // atmost the count of minimum // frequency in the s // Function to find the maximum // possible prefix of the s function MaxPrefix(s) { // Hash map to store the frequency // of the characters in the s var Dict = {}; // Iterate over the s to find // the occurrence of each Character for (const i of s) { if (Dict.hasOwnProperty(i)) { Dict[i]++; } else { Dict[i] = 1; } } var minfrequency = 2147483647; // Minimum frequency of the Characters for (const [key, value] of Object.entries(Dict)) { minfrequency = Math.min(minfrequency, value); } var countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map for (const [key, value] of Object.entries(Dict)) { if (Dict[key] === minfrequency) countminFrequency += 1; } var mapper = {}; var indi = 0; // Loop to find the maximum possible // length of the prefix in the s for (const i of s) { if (mapper.hasOwnProperty(i)) { mapper[i]++; } else { mapper[i] = 1; } // Condition to check if the frequency // is greater than minimum possible freq if (mapper[i] > countminFrequency) break; indi += 1; } // maxprefix s and its length. document.write(s.substring(0, indi)); } // Driver Code // s is initialize. var str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str); </script> |
Output:
aabcd
Performance Analysis:
- Time Complexity: In the above-given approach, there is one loop to find the frequency of each character in the string which takes O(N) time in the worst case. Therefore, the time complexity for this approach will be O(N).
- Space Complexity: In the above-given approach, there is extra space used to store the frequency of characters. Therefore, the space complexity for the above approach will be O(N)
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.
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
