Given a String array words contains words and an integer array score contains score of each word such that score[i] represents score of word at ith position. Find the max score you can achieve using the combination of words with following rules :
you're given limit integer value, the combination of words used to get maxscore cannot exceed the size limit provided in limit value.
any word can be used multiple times . Eg: words=[sun,moon] score=[5,4] limit=7 then maxscore=10 as the score of combination "sunsun"=5+5=10 and has size 6 which is less than limit 7, hence condition is satisfied.
words are allowed to overlap and form new word. After overlap, the new word can have combined power. Eg. words=[energy, green] score=[4,3] limit=9 then we can use new formed word greenergy with score value =(4+3)=7 here maxscore=7 as greenergy having score=7 and size=9 can be used here
Constraints:
1 <= n <= 100
words array contains unique words
Sample Input
Input: n=3 words=["pack", "acknowledge", "edged"] score=[2,12,3] limit=13 Output: 15 Explaination: Here new combination can be ["pack", "acknowledge", "edged", "acknowledged", "packnowledge", "packnowledged"] with score=[2, 12, 3, 15, 14, 17] So, packnowledged can picked from the combination to form maxscore=17 it also maintain the word limit rule that - size(packnowledged) <= limit 13 <= 13, hence maxscore = 17 as answer.
Does anyone know how to solve this?
I was thinking of DP where the state is the current length and the latest word we've taken ($$$N^2$$$)
Then for the transition we can always try all possible words and see whether it's overlapping or not from the latest word (another $$$N$$$)
To determine the overlapping part, since $$$N$$$ is pretty small, I think we can precompute the overlapping prefix-suffix using a bruteforce method (should be around $$$N^3$$$)
what if there are complete overlaps like ledge knowledgement ? I think prefix and suffix won't work for those scenarios.
What is the constraint on the limit value?