Sorting a custom 2D vector throws a runtime error. How do I fix this?

Question

I am trying to sort the 2D vector on basis of the difference between the character count of a particular character and the rest of the characters. It works fine for most of the test cases, but it seems to fail for this particular testcase. After some debugging, I found out that it is getting a runtime error when ch='d' and ch='e' for the following testcase. I am not able to figure out what exactly is happening here.

Link to the question:-

https://codeforces.com/contest/1551/problem/C

My Logic:- For each character{a-z} say ch, which could be the deciding character to have the maximum occurrence after deleting some strings, I am trying to eliminate the strings with the max difference of frequency of ch minus the other characters.

typedef long long int ll;
void solve()
{
    ll n;
    string s;
    cin>>n;
    vector<vector<ll>>v(n,vector<ll>(5,0));
    unordered_map<char, ll>m;
    vector<string>str;
    unordered_map<char, ll>old;
    for(ll i=0;i<n;i++)
    {   
        cin>>s;
        str.push_back(s);
    }
    for(ll i=0;i<n;i++)
    {   
        for(ll j=0;j<str[i].length();j++)
        {
            v[i][str[i][j]-97]++;
            m[str[i][j]]++;
        }
    }
    old=m;
    ll ans=0;
    for(char ch='a';ch<='e';ch++)
    {  
        m=old;
        ll sum=m['a']+m['b']+m['c']+m['d']+m['e'];
        if(sum-m[ch]<m[ch])
        {
            ans=max(ans,n);
        }
        sort(v.begin(),v.end(),[ch](const vector<ll>&a,const vector<ll>&b)
        {   
            return (a[ch-97]-(a[0]+a[1]+a[2]+a[3]+a[4]))<=(b[ch-97]-(b[0]+b[1]+b[2]+b[3]+b[4]));
        });
     
        for(ll i=0;i<n;i++)
        {   
            for(ll j=0;j<5;j++)
            {   
                m[j+97]=m[j+97]-v[i][j];
            }
            ll sumrest=m['a']+m['b']+m['c']+m['d']+m['e'];
            if(m[ch]>sumrest-m[ch])
            {
                ans=max(ans,n-i-1);
            }  
        }
    }
    cout<<ans<<"\n";
}

Testcase:-

1
43
a
d
bbc
a
dda
c
e
bb
cbd
c
dc
e
caab
d
c
e
e
bd
d
a
a
b
a
c
d
c
d
ba
e
c
ecdb
bdbd
d
e
cb
ac
ccd
cb
cda
da
bb
d
c

Answer 1

The answer to your question regarding the sorting has already been given in a comment. Your Lambda that you provided does not fulfill the requirements of strict weak ordering. So, if you want to continue with your approach, then you need to change the Lambda.

Unfortunately, I have to say that your design is wrong and that you started with writing code too early. I will show you a better strategy on how to solve such problems.

As in the classical approach of software development, we should start with Requirements Elicitation/Requirements Analysis. The result of that will be used for the Design/Detailed Design. Because of the simplicity of the task, we can skip the detailed design.

In most cases, the description of the problem in text form by Codeforces (and other such sites) is always somehow complicated, so, a requirements analysis is mandatory.

Stephen Queen wants to write a story. He is a very unusual writer, he uses only letters 'a', 'b', 'c', 'd' and 'e'!

Eliminating the noise, the requirement is:

• use ‘a’,’b’,’c’,’d’,’e’ as data elements. The data elements are consecutive

To compose a story, Stephen wrote out n words consisting of the first 5 lowercase letters of the Latin alphabet. He wants to select the maximum number of words to make an interesting story.

Eliminating the noise, the requirement is:

• There will be a given number of words (n)
• We need to find the maximum number of those words following a certain condition

Let a story be a sequence of words that are not necessarily different. A story is called interesting if there exists a letter which occurs among all words of the story more times than all other letters together.

Eliminating the noise, the requirement is:

• In the list of words there may be duplicates
• The condition to select words so that the sum of one selected character (‘a’,’b’,’c’,’d’,’e’) is greater than the sum of all other characters together
• Summation will be done for 1 or more words in the list of words

For example, the story consisting of three words "bac", "aaada", "e" is interesting (the letter 'a' occurs 5 times, all other letters occur 4 times in total). But the story consisting of two words "aba", "abcde" is not (no such letter that it occurs more than all other letters in total). You are given a sequence of n words consisting of letters 'a', 'b', 'c', 'd' and 'e'. Your task is to choose the maximum number of them to make an interesting story. If there's no way to make a non-empty story, output 0.

Eliminating the noise, the requirement is:

• Output number of words that fulfill the condition (or 0, if none)

Input. The first line contains one integer t (1≤t≤5000) — the number of test cases. Then t test cases follow. The first line of each test case contains one integer n (1≤n≤2⋅10 5) — the number of the words in the sequence. Then n lines follow, each of them contains a word — a non-empty string consisting of lowercase letters of the Latin alphabet. The words in the sequence may be non-distinct (i. e. duplicates are allowed). Only the letters 'a', 'b', 'c', 'd' and 'e' may occur in the words.

Eliminating the noise, the requirement is:

• First Input is the number of test case
• The range of test case is 1-5000
• Then all test cases follow
• Each test case starts with the number of words
• Words are none empty, maybe duplicate and consist of the elements described above

It is guaranteed that the sum of n over all test cases doesn't exceed 2⋅10 5; the sum of the lengths of all words over all test cases doesn't exceed 4⋅10 5.

Eliminating the noise, the requirement is:

• There will be a maximum of 2 10 5 words overall
• All words together will have only a length of 4 10 5

Output: For each test case, output the maximum number of words that compose an interesting story. Print 0 if there's no way to make a non-empty interesting story.

Eliminating the noise, the requirement is:

• Show the result of each testcase in a separate row

So, this are all requirements:

• use ‘a’,’b’,’c’,’d’,’e’ as data elements. The data elements are consecutive

Summary of Requirements

1. There will be a given number of words (n)
2. We need to find the maximum number of those words following a certain condition
3. In the list of words there may be duplicates
4. The condition to select words so that the sum of one selected character (‘a’,’b’,’c’,’d’,’e’) is greater than the sum of all other characters together
5. Summation will be done for 1 or more words in the list of words
6. Output number of words that fulfill the condition (or 0, if none)
7. First Input is the number of test cases
8. The range of test case is 1-5000
9. Then all test cases follow
10. Each test case starts with the number of words
11. Words are none empty, maybe duplicate and consist of the elements described above
12. There will be a maximum of 2 10 5 overall words
13. All words together will have only a length of 4 10 5
14. Show the result of each testcase in a separate row
15. use ‘a’,’b’,’c’,’d’,’e’ as data elements. The data elements are consecutive

Now, we can start with the design.

(1), (10) (12): Number of words will be given at runtime. Maximum number is known --> We will use a std::vector of std::string to store the words

(3): not relevant

(12), (13). The data type unsigned int is sufficient to store all values

(5): We need to operate on all words in the list, until we find a result.

(4): This is the most important one and describes the algorithm. Let us start with just one letter for the beginning. We will later simply expand the solution for all other letters as well.

So, what we need to do is counting all ‘a’ letters. And obviously also all other letters. And for a good result, Count ‘a’ must be greater than Count ‘others’ So:

Count ‘a’ > Count ‘others’      or     Count ‘a’ - Count ‘others’ >0

This means, we can increment a counter if we find an ‘a’ and then decrement the counter for all other letters.

(5) And this counting will be done for each word in the list.

(6) We need to select the number of words, for which the condition: Counter > 0 is met. So, in order to achieve that, we need to sort the counters from greatest to smallest and add them up. As soon as the sum is smaller that 0, the word does not belong to the result set.

(2) We do (6) (14) for all letters, and find out the maximum number of results for that letter. That will be output to std::cout

(7), (8). At the beginning read the number of test cases into an unsigned integer.

(9) Evaluate all test cases.

(15) A word has 5 elements. They are consecutive. We can use simple loops to operate on them.

(8), (11), (12), (13), (15). All values are defined. Input range is clear. Max data type need is unsigned integer. Letter will be stored as char. No input validation necessary. No initialization of variables before reding from std::cin necessary, because all input values are guaranteed to be correct.

Here is one possible solution:

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>

constexpr std::array<char, 5> Letters{{'a','b','c','d','e'}};

int main() {
    // Get number of test cases
    unsigned int numberOfTestCases; std::cin >> numberOfTestCases;
    
    // Work on all test cases
    while (numberOfTestCases--  > 0) {
        
        // Now, read the number of words that will be used in this test cases
        unsigned int numberOfWords; std::cin >> numberOfWords;
        
        // Here we will store all words for thsi test case. Number is known
        std::vector<std::string> words(numberOfWords);
        
        // Read all words from std::cin for this test case
        for (std::string& word : words) std::cin >> word;
        
        // Here we will store the result overall for this test case
        size_t resultForThisTestCase{};
        
        // Now make the evaluation for all Letters
        for (const char letter : Letters) {
        
            // We will count all occurences for this letter 
            // (subtracted by other letters) for all words
            std::vector<int> letterCounter(numberOfWords);
            
            // Check all words of this test case
            for (size_t wordIndex{}; wordIndex < numberOfWords; ++wordIndex) 
            {
                // Evaluate all letters of this word and count up or down
                for (const char c : words[wordIndex])
                    if (letter == c)
                        ++letterCounter[wordIndex];
                    else
                        --letterCounter[wordIndex];
            }
            
            // Sort counters for this one letter from large to small,
            // because only the big numbers are relevant
            std::sort(letterCounter.begin(), letterCounter.end(), std::greater<int>());
            
            // Now, for all counters of the words and as long as counts are positive (meaning
            // the count of this letter is larger than for all other letters)
            int sumOfCounters{};
            
            for (size_t counterIndex{}; counterIndex < numberOfWords; ++counterIndex) {
                
                // Sum up counters
                sumOfCounters += letterCounter[counterIndex];
                
                // End condition. If count of this letter is smaller than the count of
                // all other letters, then this word does not belong to the result
                if (sumOfCounters <= 0) break;
                
                // We are still looping, so this counter contributes to the result
                // Count it and also take the max from all other evaluated letters, since
                // the only required info, is the number of words (regardless of the letter)
                resultForThisTestCase = std::max(resultForThisTestCase, counterIndex + 1);
            }
        }  // And this is the result . . .
        std::cout << resultForThisTestCase << '\n';
    }
    return 0;
}