Recently, I've been working on a Leetcode problem. In this problem, I tried to create a std::map<string, int> and instead of comparing the string based on alphabetical order, I want to compare them based on their lengths. However, the map ends up having weird entries count.
int maximumLength(string s) {
int n = (int)s.length();
auto comp = [&](const string& s1, const string& s2) { return (int)s1.length() < (int)s2.length(); };
map<string, int, decltype(comp)> msi(comp);
// map<string, int, LengthComparator> msi;
for (auto i = 0; i < n; i++) {
for (auto j = 1; j < n - i + 1; j++) {
string tmp = s.substr(i, j);
cout << tmp << endl;
msi[tmp] += 1;
}
debug(msi);
}
int res = -1;
for (auto it = rbegin(msi); it != rend(msi); it++) {
cout << it->first << " " << it->second << endl;
// if (it->second >= 3) {
// res = (int)it->first.length();
// break;
// }
}
return res;
}
int32_t main() {
string input{"abcdef"};
cout << maximumLength(input) << endl;
return 0;
}
The output:
a
ab
abc
abcd
abcde
abcdef
[msi] = [{("a",1),("ab",1),("abc",1),("abcd",1),("abcde",1),("abcdef",1)}]
b
bc
bcd
bcde
bcdef
[msi] = [{("a",2),("ab",2),("abc",2),("abcd",2),("abcde",2),("abcdef",1)}]
c
cd
cde
cdef
[msi] = [{("a",3),("ab",3),("abc",3),("abcd",3),("abcde",2),("abcdef",1)}]
d
de
def
[msi] = [{("a",4),("ab",4),("abc",4),("abcd",3),("abcde",2),("abcdef",1)}]
e
ef
[msi] = [{("a",5),("ab",5),("abc",4),("abcd",3),("abcde",2),("abcdef",1)}]
f
[msi] = [{("a",6),("ab",5),("abc",4),("abcd",3),("abcde",2),("abcdef",1)}]
abcdef 1
abcde 2
abcd 3
abc 4
ab 5
a 6
-1
There's no way there are 6 a's in my string. So, I wonder where it went wrong. If I remove the comp function it behaves as expected.
I'm using C++23 (Leetcode default). I tried to run with C++14 onward, but same problem.
(here is the essence of my original comment posted as an answer, as requested)
Your custom comparator is not able to distinguish between two strings of the same length, because nowhere do you compare the actual contents of the string.
For ordered containers, the definition of equality is !comp(x, y) && !comp(y, x). In other words: when neither x or y is less than the other, they are deemed equal.
That means every string of the same length will resolve to the same map node, and the key for that node will be whatever string resulted in the node being created. That's why you're seeing a count of 6 for "a" and so on. It's not that you encountered "a" 6 times, but you did encounter 6 strings of length 1.
Here is how you can define an ordering that uses length as the primary criteria, followed by content as the secondary criteria:
auto comp = [](const string& s1, const string& s2) {
return s1.length() < s2.length()
|| s1.length() == s2.length() && s1 < s2;
};