Total Variety of Substrings

Hard

Call the **variety** of a string the number of distinct letters in it. For example, the variety of "banana" is 3, since it only uses a, b and n. You are given a string text. Take every non-empty substring, that is, every contiguous piece of the string; pieces with the same content at different positions count separately. Return the sum of their varieties. Listing all substrings costs O(n²) or more; try to get away with a single pass.

Example 1

text='kayak' → 30

The one-letter substrings give 5. The two-letter ones "ka", "ay", "ya", "ak" give 2 each, 8 in total. The three-letter ones "kay", "aya", "yak" give 3 + 2 + 3 = 8. The four-letter ones "kaya" and "ayak" give 3 each, 6 in total. The whole string gives 3. The sum is 5 + 8 + 8 + 6 + 3 = 30.

Example 2

text='mmm' → 6

There are six substrings, and each of them has exactly one distinct letter.

Example 3

text='xyz' → 10

Constraints

1 ≤ len(text) ≤ 10⁵
text consists of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Dynamic Programming

Similar problems

Every Way to Space the Words Hard Lone Letters in Every Substring Hard Length of a Growing Word Hard Make Letter Counts Equal Hard Split Into Dictionary Words Medium

Input

text='kayak'

Expected

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.