Ctrl K

Counting Distinct Substrings

Medium
You are given a string text. A piece is any non-empty contiguous part of it, that is, what remains after removing some characters from the start and some from the end (possibly none). Return how many distinct strings appear among the pieces. Identical pieces found in different places count only once. A straightforward solution is easy to see; try to find one that does not store every piece in full.
Example 1
text='abab' → 7

The distinct pieces are "a", "b", "ab", "ba", "aba", "bab" and "abab": seven of them. Repeats of "a", "b" and "ab" count once.

Example 2
text='zzz' → 3

Only "z", "zz" and "zzz".

Example 3
text='abc' → 6
Constraints
  • 1 ≤ text.length ≤ 500
  • text consists of lowercase English letters
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsLongest Piece Seen Twice MediumTarget From Word Beginnings MediumLongest Repeated Fragment HardDoubled Fragments HardSuffixes Echoing the Start Hard
loading Python…
Input
text='abab'
Expected
7

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