Lone Letters in Every Substring

Hard

Call a letter of a substring lone if it occurs in that substring exactly once. For instance, in "BANANA" only B is lone, while in "ANT" all three letters are. Given a string word, count the lone letters of every non-empty substring and return the sum of those counts. Substrings with the same text at different positions are counted separately. Checking every substring is too slow; aim for linear time.

Example 1

word="AB" → 4

The substrings are "A" (1), "B" (1) and "AB" (2), for a total of 4.

Example 2

word="AAB" → 6

"A", "A" and "B" give 1 each, "AA" gives 0 (its letter repeats), "AB" gives 2 and "AAB" gives 1 (only B is alone). The total is 6.

Example 3

word="ZZZ" → 3

Constraints

1 ≤ len(word) ≤ 10⁵
word consists of uppercase English letters
The answer fits in a 32-bit integer

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 Total Variety of Substrings Hard Length of a Growing Word Hard Make Letter Counts Equal Hard Split Into Dictionary Words Medium

Input

word="AB"

Expected

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