HardNo. 2223
Sum of Scores of Built Strings — LeetCode 2223 Python Solution
- Pattern
- Monotonic Stack
- Topics
- String, Binary Search, String Matching, Suffix Array, Hash Function, Rolling Hash
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled si.
Example
- Input
- s = "babab"
- Output
- 9
- Explanation
- For s1 == "b", the longest common prefix is "b" which has a score of 1.
Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 2223. Sum of Scores of Built Strings is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1923 | Longest Common Subpath | Hard |
| 0902 | Numbers At Most N Given Digit Set | Hard |
| 1268 | Search Suggestions System | Medium |
| 2055 | Plates Between Candles | Medium |
| 2468 | Split Message Based on Limit | Hard |
| 2226 | Maximum Candies Allocated to K Children | Medium |
Frequently asked questions
- How hard is LeetCode 2223. Sum of Scores of Built Strings?
LeetCode 2223. Sum of Scores of Built Strings is rated Hard on LeetCode.
- What topics does LeetCode 2223. Sum of Scores of Built Strings cover?
LeetCode 2223. Sum of Scores of Built Strings is tagged String, Binary Search, String Matching, Suffix Array, Hash Function and Rolling Hash on LeetCode.