Count Unique Characters of All Substrings

HardStringshashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

For a string t, let unique(t) be the number of characters that occur **exactly once** in t. For example, unique("ABCA") = 2 because only B and C appear once. Given a string s of uppercase English letters, return the sum of unique(t) over **every substring** t of s. Substrings are counted by position, so equal substrings starting at different indices each contribute separately. Aim for O(n) time: counting each substring directly is far too slow for long inputs. The answer fits in a 32-bit signed integer.

Examples

Input: s = "ABA"
Output: 8
Substrings: `A`(1), `B`(1), `A`(1), `AB`(2), `BA`(2), `ABA`(1, only `B`). Total 8.
Input: s = "XYZ"
Output: 10
Every character is distinct, so each substring contributes its length: 1+1+1+2+2+3 = 10.

Constraints

  • `1 <= s.length <= 10^5`
  • `s` consists of uppercase English letters only

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More hashing problems