DiffPush Tier Tries · Problems O(n^2) · O(n^2)
A stadium anthem archive studies crowd chants. Analysts slice a chant recording into every contiguous syllable run and want to know how many unique runs exist — duplicates collapse into one. The empty run counts too. Two runs are the same only when their syllables match exactly.
Input: A string s of lowercase letters.
Output: Return the number of distinct substrings of s, including the empty substring.
1 <= len(s) <= 1000s uses lowercase English lettersInput: {"s":"abab"}
Output: 8
Distinct non-empty runs: a, b, ab, ba, aba, bab, abab — 7 of them; the canonical count adds the empty run for 8.
Input: {"s":"aaa"}
Output: 4
a, aa, aaa plus the empty run.