Explanation of an O(N) solution


  • -1

    This thread will introduce an O(N) solution, where N is the summation of all lengths of the strings.


    Notations:

    For a string
    s, let N(s) be the length of the string s. Let the set F(s) be all subsets of the set of characters that do not appear in the string s.

    Example,

    s = "abcefghijlmnopqrstuvwxyz" (this string contains all characters from 'a' to 'z' except 'd' and 'k')

    N(s) = 24 (26-2=24)

    F(s) = {"", "d", "k", "dk"} (powerset of "dk")

    We can get F(s) in O(N(s)) time. The cardinality of F(s) is no more than 2^26. That is, |F(s)| = O(1).

    Additionally, we maintain an unordered_map m, whose keys are the subsets of the alphabet, and the corresponding value is the largest length of strings that does not contains the characters in the entry. The size of m is 2^26 = O(1).


    Algorithm Outline:

    We only need two O(N) passes to solve this problem:

    • Pass 1:
      For each string s, we need O(N(s)) time to calculate F(s), then need O(1) time to update the entry f of F(s) in a map by m[f] = max(m[f], N(s)).

    • Pass 2:
      For each string s, we need O(N(s)) time to calculate F(s), then need O(1) time to find maximum of m[f], where f belongs to F(s). Here we get a potential candidate of result: N(s) * max(m[f]). Then update the result accordingly by result = max(result, N(s) * max(m[f])).


    Complexities:

    • Time: O(N)

    • Space: O(1)


  • 0
    I

    Assume you have a string s=abcde and you check F(s). F(s) contains f=abc, you go to m[f] that may contain dezzzzzzzzz (as you see it does not contain characters a, b, or c). Then you multiply s with m[f] which is wrong! No?


  • 0
    This post is deleted!

  • 0
    K

    Also if you only process only non-empty strings you can knockdown the cardinality of F(s) to at most 2^25. Also when you code it up you will get a TLE


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.