Skip to content
Get started

Distinct substrings of BARBARIAN

How many distinct non-empty contiguous substrings does the word barbarian have? (Substrings are compared as strings, so bar counts once however often it occurs.)

Show hints (3)+
  1. Every substring is a prefix of at least one suffix - count it only at the first suffix (in sorted order) that has it.
  2. Sort the 9 suffixes and compute each one's longest common prefix with its predecessor.
  3. Answer =45−∑LCP= 45 - \sum \text{LCP}.

Answer

Reveal answer →

38

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions