For this problem, I preferred to convert each string I was comparing to a hash map of characters to count the occurrence of each letter. Since std::map is ordered, by comparing the occurrences of the first letter in either map, I was able to see if a string was strictly smaller very easily. Here’s my solution. Note I have a helper function to convert a string into a std::map.
#include // copy
#include // cin, cout
#include // back_inserter, istream_iterator, ostream_iterator, prev
#include // istringstream
#include // getline, string
#include // vector
#include
std::map<char, int> strToMap(const std::string inStr) {
std::map<char, int> map;
for(const char c : inStr) {
if(map.count(c) == 0) {
map[c] = 1;
}
else {
map[c]++;
}
}
return map;
}
std::vector compare_strings(std::vectorstd::string str1, std::vectorstd::string str2) {
std::vector output;
for(const std::string str2_current : str2) {
std::map<char, int> str2Map = strToMap(str2_current);
int numSmaller = 0;
for(const std::string str1_current : str1) {
std::map<char, int> str1Map = strToMap(str1_current);
if(str1Map.begin()->second < str2Map.begin()->second) {
numSmaller++;
}
}
output.push_back(numSmaller);
}
return output;
}
We can leverage on the fact that it is only lowecase english letters.
so fixed size for the count array of the helper function.
we can also precalculate the frequencies for str1 instead of recaluclate it every time.
from typing import List
def smallest_freq(some_str):
"""since we have a fixed length made up of lowercase english chars"""
chars_count = [0]*26
for c in some_str:
index_c = ord(c) - ord('a')
chars_count[index_c]+=1
for count in chars_count:
if count >0:
return count
def compare_strings(str1:List[str],str2:List[str]) -> List[int]:
A = [0]*len(str2)
freq_str1 = [smallest_freq(ss) for ss in str1]
for i in range(0,len(str2)):
k = smallest_freq(str2[i])
for v in freq_str1:
if v<k:
A[i]+=1
return A
``