#2223
Sum of Scores of Built Strings
candidate master · 1555 · lc hard +32 · verified · 46.9% accepted · 298 likes · top 31%
Description
A string s of length n is built one character at a time by prepending each new character to the front. The resulting strings are labeled s1 through sn, where si has length i.
- For example, for s = "abaca": s1 == "a", s2 == "ca", s3 == "aca", and so on.
The score of each si is the length of its longest common prefix with sn (the full string s).
Given the final string s, return the sum of scores of all strings s1 through sn.
Example 1:
Input: s = "babab"
Output: 9
Explanation:
For s1 == "b", the longest common prefix is "b" which has a score of 1.
For s2 == "ab", there is no common prefix so the score is 0.
For s3 == "bab", the longest common prefix is "bab" which has a score of 3.
For s4 == "abab", there is no common prefix so the score is 0.
For s5 == "babab", the longest common prefix is "babab" which has a score of 5.
The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.
Example 2:
Input: s = "azbazbzaz"
Output: 14
Explanation:
For s2 == "az", the longest common prefix is "az" which has a score of 2.
For s6 == "azbzaz", the longest common prefix is "azb" which has a score of 3.
For s9 == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
For all other si, the score is 0.
The sum of the scores is 2 + 3 + 9 = 14, so we return 14.
Code
1
2
3