Sum of Scores of Built Strings — LeetCode 2223 Python Solution
HardStringBinary SearchString MatchingSuffix ArrayHash FunctionRolling Hash
- Problem
- #2223
- Pattern
- Monotonic Stack
- 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
| Measure | Complexity |
|---|---|
| Time | O(log n) or O(n log n) |
| Space | O(1) auxiliary |
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
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.