Given a string find the character which occurs a minimum number of times.
Note: If multiple such characters exist output anyone.
Example:
Input: S = abbccdd
Output: a
As frequency of every element is more than that of a
Input: S = abccdd
Output: b or Output: a
Both the outputs are acceptable according to given conditions.
Naive Approach:
We can run nested loops and keep the counter for a minimum frequency and can compare it with the frequency of each element found in one pass of for loop.
Complexity: O(n2)
Better Approach:
As there are only 26 characters in the English language we can safely assume the complexity of unordered_map in c++ or any Hash Table function to be O(1) in case searching.
We may even use a frequency array of size 26 in this approach instead of unordered_map
//Programm to find character occuring minimum number of times. #include<bits/stdc++.h> using namespace std; char minFreq(string s) { unordered_map<char,int>freq; // for counting frequency of each character int min=INT_MAX; char ans; // this is to be returned st last for(auto x:s) // Counting frequency of each character freq[x]++; for(auto x:freq) //Finding Character With MIN FREQ { if(x.second<min) { min=x.second; ans=x.first; } } return ans; } int main() { string s="Cplusplus"; cout<<"Character With MIN FREQ :"<<minFreq(s); return 0; }
Output
Character With MIN FREQ :C