# Explanation of an O(N) solution

• 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)

• 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?

• This post is deleted!

• 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

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