855. Count Prefix AppearancesPOTD
Given a string s of length n, the task is to count the number of occurrences of each prefix of the string in the entire string. For a prefix defined as s[0...i] (where i ranges from 0 to n-1), determine how many times this prefix appears as a substring within s.
Example 1:
Input: s = "abab"
Output: [2, 2, 1, 1]
Explanation:
Prefix s[0...0] = "a" appears 2 times.
Prefix s[0...1] = "ab" appears 2 times.
Prefix s[0...2] = "aba" appears 1 time.
Prefix s[0...3] = "abab" appears 1 time.
Example 2:
Input: s = "aaaa"
Output: [4, 3, 2, 1]
Explanation:
Prefix s[0...0] = "a" appears 4 times.
Prefix s[0...1] = "aa" appears 3 times.
Prefix s[0...2] = "aaa" appears 2 times.
Prefix s[0...3] = "aaaa" appears 1 time.
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= s.length <= 105