### AJ__20's blog

By AJ__20, history, 4 months ago, You are given an array of strings A of size N. You need to pick two strings Ai and Aj such that len(Ai)* len(Aj) is maximized. Thanks in advance. Edit : Sry, forgot to add the constraints : there was a condition stating those two strings should have no common characters, then what would be the optimal solution ? Comments (11)
 » You can't do that in less than O($\text{total length of all strings}$) since you need to read the strings.
 » 4 months ago, # | ← Rev. 2 →   I don't think there is any more optimal way than this? Spoiler//can use long long depending on the constraints #include using namespace std; int main(){ int n; cin >> n; int mxValOne = -1, mxValTwo = -1; for(int i = 0; i < n; i++){ //reading the strings string s; cin >> s; int len = s.size(); if( len >= mxValOne ){ //inserting the max value in the secondMax mxValTwo = mxValOne; //jupdating the max Len with the currLen mxValOne = len; } else if( len > mxValTwo ) mxValTwo = len; } //maxLen * secondMaxLen; cout << mxValOne * mxValTwo; } 
•  » » 4 months ago, # ^ | ← Rev. 2 →   Correct idea, but the code is wrong. You forgot to test if the length of a given string is smaller than the largest but larger than the second largest. Input: 3 a abc ab Correct Output: 6 Your Output: 3  Corrected code#include using namespace std; int main(){ int n; cin >> n; int mxValOne = -1, mxValTwo = -1; for(int i = 0; i < n; i++){ //reading the strings string s; cin >> s; int len = s.size(); if(len >= mxValOne){ //inserting the max value in the secondMax mxValTwo = mxValOne; //jupdating the max Len with the currLen mxValOne = len; } else if(len >= mxValTwo){ //jupdating the secondMax Len with the currLen mxValTwo = len; } } //maxLen * secondMaxLen; cout << mxValOne * mxValTwo; } // it would be embarrassing if this was still incorrect 
•  » » » thanks, my bad. Updated the code.
•  » » » Could you please tell the optimal approach for the modified question?
•  » » » » can you please tell what are the constraints on the length of the array of strings?
•  » » » » » That was was asked in test, i forgot the constraints but i tried brute force solution and got tle. My solution is n*n*n, so i was thinking what would be the optimized approach
•  » » » » » » I guess, you can use bitmasking for this approach, wait lemme write it with the code. Time Complexity AnalysisTC: O((n * m) + (n * n)), where*m is length of maximum length string, n is count of strings. SC: O(n), pair to store length and mask [used bitmasking in the problem] [don't know if it can be done in a better way] code#include using namespace std; int main(){ int n; cin >> n; vector> pr; for(int i = 0; i < n; i++){ string s; cin >> s; int len = s.size(); int mask = 0; for(auto &a : s) mask |= 1 << (a - 'a'); pr.emplace_back(mask, len); } int mxProd = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if( (pr[i].first & pr[j].first) == 0 ){ mxProd = max(mxProd, pr[i].second * pr[j].second); } } } cout << mxProd; return 0; } 
•  » » » » » » » Thanks :)
 » Auto comment: topic has been updated by AJ__20 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by AJ__20 (previous revision, new revision, compare).