AJ__20's blog

By AJ__20, history, 17 months ago, In English

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 ?

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?
»
17 months ago, # |
  Vote: I like it +17 Vote: I do not like it

You can't do that in less than O($$$\text{total length of all strings}$$$) since you need to read the strings.

»
17 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

I don't think there is any more optimal way than this?

Spoiler
  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      thanks, my bad. Updated the code.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please tell the optimal approach for the modified question?

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please tell what are the constraints on the length of the array of strings?

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            I guess, you can use bitmasking for this approach, wait lemme write it with the code.

            Time Complexity Analysis
            code