I want to create a function that takes in a string as a parameter and checks if the number of occurrences of the individual letters are different.
"OBDO" should display NO, because O occurs twice, but B and D occur once.
"AABBB" should display YES, because A occurs twice, and B occurs three times.
My code seems to work, but my code auto checker wont accept it, out of 4 tests it only passes once. I believe this can be done way better and shorter.
Can anyone advise?
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct custom_comparator {
bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) const
{
return less_comparator(std::minmax(a.first, a.second),
std::minmax(b.first, b.second));
}
std::less<std::pair<int, int>> less_comparator;
};
int main()
{
string word;
string notDupes = "";
vector<int> amount;
vector<pair<char,int>> para;
std::set<std::pair<char, int>, custom_comparator> unique;
vector <int> items;
vector <char> toIterate;
string result;
while(cin>>word) {
if(word.length() > 100) {
return 0;
}
for( int x=0;x<word.length();x ) {
int isUpper = isupper(word[x]);
if(!isUpper) {
return 0;
}
}
for(int i =0;i<word.length();i ) {
int times = std::count(word.begin(), word.end(), word[i]);
para.push_back({word[i], times});
}
for(int pl=0;pl<para.size();pl ) {
unique.insert(para[pl]);
}
for (auto p : unique) {
toIterate.push_back(p.first);
items.push_back(p.second);
}
auto it = std::unique(items.begin(), items.end());
bool wasUnique = (it == items.end());
if(wasUnique) {
result = "YES";
} else {
result = "NO";
}
cout << result << endl;
}
return 0;
}
CodePudding user response：
You can reduce the whole thing (if I understood the question correctly) to just a few rather simple steps:
- Sort the input string, so duplicate characters end up next to each other.
- produce a list (or vector) of the occurrence counts of each distinct character.
- test, if the list (or vector) of those occurrence counts contains duplicates.
- If duplicates - output "NO" else output "YES".
step 1 is easily done, using std::sort.
step 2 is not quite as obvious- but a std::accumulate (similar to reduce and also often called fold) can help with that, if we maintain the current counting and listing state in the accumulator of the operation, while iterating over the sorted strings characters.
step 3, we can do by using a std::set<size_t>, inserting the resulting list from step 2 into it and then compare the size of the set with the size of the list.
In C , this can look like this:
#include <iostream>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
struct Accumulator {
char current;
size_t count;
std::vector<size_t> occurrences;
Accumulator(char c, size_t count, std::vector<size_t> occs)
: current{c}
, count{count}
, occurrences{occs}
{
}
};
int main (int argc, const char* argv[]) {
if (argc >= 1) {
std::string s = argv[1];
auto sorted_s = s;
std::sort(sorted_s.begin(),sorted_s.end(),std::less<char>());
Accumulator x =
std::accumulate(sorted_s.cbegin() 1,
sorted_s.cend(),
Accumulator(*sorted_s.cbegin(),1,{}),
[](Accumulator acc, char c) {
if (c == acc.current) {
return Accumulator(c,
acc.count 1,
acc.occurrences);
} else {
auto acc1 = Accumulator(c,1,acc.occurrences);
acc1.occurrences.push_back(acc.count);
return acc1;
}
});
x.occurrences.push_back(x.count);
std::set<size_t> deduped;
for (auto& k : x.occurrences) {
deduped.insert(k);
}
if (deduped.size() == x.occurrences.size()) {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
} else {
std::cout << "no input." << std::endl;
}
return 0;
}
And it is easily ported to other languages, offering about the same facilities. Here, for example the less verbose implementation in Common Lisp:
(defun unique-occurrence-counts-of-chars
(s)
(let ((sorted-s (sort (copy-seq s) #'char<)))
(let ((x
(reduce #'(lambda (acc c)
(if (char= (first (first acc)) c)
(list
(list c ( (second (first acc)) 1))
(second acc))
(list
(list c 1)
(cons (second (first acc))
(second acc)))))
(subseq sorted-s 1)
:initial-value (list (list (aref sorted-s 0) 1)
'()))))
(let ((y (cons (second (first x)) (second x))))
(let ((deduped-y (remove-duplicates y)))
(if (= (length y) (length deduped-y))
"yes"
"no"))))))
and even terser in Haskell:
import qualified Data.Set as Set
import Data.List
unique_occurrence_counts_of_chars:: String -> String
unique_occurrence_counts_of_chars s =
let folder ((current, count),occs) c =
if current == c
then
((c, count 1), occs)
else
((c, 1), (count : occs)) in
let sorted_s = sort s
x = foldl folder ((head sorted_s, 1), []) (tail sorted_s)
y = (snd (fst x)) : (snd x)
yDeduped = Set.fromList y
in if ((length . Set.toList) yDeduped == length y)
then "Yes"
else "No"
CodePudding user response：
As mentioned in the comments, the requirements seem to be easily accomplished by utilizing a std::map or std::unordered_map, and then seeing if the map size is equal to the number of items in the original string.
Here is an example:
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
std::string Solution(std::string word)
{
// Verify the entire string is upper case
if ( !std::all_of(word.begin(), word.end(),
[](unsigned char c)
{ return std::isupper(c);}))
return "NOT VALID";
// get a count of each character in the string
std::map<char, int> sMap;
for (auto c : word)
sMap[c] ;
// Now go through the built-up map and insert the counts
// into the set
std::set<int> sCount;
for (auto& pr : sMap)
sCount.insert(pr.second);
// Return "YES" if the set.size() is equal to the
// map size
if ( sCount.size() == sMap.size() )
return "YES";
return "NO";
}
int main()
{
std::cout << Solution("OBDO") << "\n";
std::cout << Solution("AABBB") << "\n";
std::cout << Solution("AA1BBB") << "\n";
}
Output:
NO
YES
NOT VALID
The std::map simply increments the frequency count for each character. The std::set is used, since a std::set does not store duplicates. All of the counts that were accumulated in the map are inserted into the set.
Then it's just a matter of checking of the std::set number of entries matches the map's number of entries.
Also note that to check if the string is all upper-case, the std::all_of algorithm function with the appropriate lambda is used.