-1

enter image description here

1 < n <= 4 x 10^5
Length of each string can be up to 11
Each string contains only uppercase letters

Example - If there are 3 strings, A, B and AE, output is 200.
Explanation - S = {"A", "B", "AE"}

Strings A and AE are prefix neighbors, so they cannot both be in Mark's subset of S. String B has no prefix neighbor, so we include it in Mark's subset.

To maximize the benefit value, we choose AE and B for our subset. We then calculate the following benefit values for the chosen subset:

Benefit value of AE = 65+69 = 134
Benefit value of B = 66

Total benefit value = 134 + 66 = 200.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
Arnav Kaushik
  • 77
  • 1
  • 8
  • So, what is the exact question? Also, if you just copy a problem from somewhere, a link attributing the source would be nice. – Gassa Feb 10 '17 at 18:37
  • It's a problem from a [HackerRank contest](https://www.hackerrank.com/contests/rookierank-2/challenges/prefix-neighbors) – EddPorter Feb 11 '17 at 22:51

1 Answers1

1

Insert the input words into a radix tree and splice out the non key words. Compute the maximum-weight independent set of the tree; the link goes to an unweighted algorithm, so you'll need to replace 1 by the weight of the node as defined by this question. All of this is linear-time.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120