1
$\begingroup$

I have been stuck on this problem for a while now; any help would be appreciated.

Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For example, "abbccbbadad" has 3 because "bb" is composed of 2 "b"s, "cc" is composed of 3 "c"s, and "adad" is composed of 2 "ad"s.

My solution uses hashing and currently runs in n^2 time, which is fine because the length of the string is <= 5000. However, my program uses n^3 space. I am confident that a solution requiring n^2 space and n^2 time will pass. Is there a more efficient solution?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by consecutive string? Do you mean a (nontrivial) power? $\endgroup$
    – Yuval Filmus
    Commented Mar 28, 2020 at 21:20
  • $\begingroup$ a substring which is just 2 or more repeats of a string, like "abcabcabc" is 3 "abc"s which are consecutive. $\endgroup$
    – pblpbl
    Commented Mar 28, 2020 at 21:22
  • 1
    $\begingroup$ The English term is power. $\endgroup$
    – Yuval Filmus
    Commented Mar 28, 2020 at 21:23

1 Answer 1

Reset to default
0
$\begingroup$

Any algorithm that runs in $O(n^2)$ time can access at most $O(n^2)$ different memory locations during the course of its execution. Thus, if you replace memory with a hashtable (instead of accessing address $a$, access the hashtable at key $a$), you obtain an algorithm with expected running time $O(n^2)$ and space $O(n^2)$. If you care about theoretical proofs, you can use a balanced binary search tree instead of a hashtable and obtain a worst-case time bound of $O(n^2 \log n)$ time and $O(n^2)$ space.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was using an unordered_map in C++ to store information about each substring, but for each substring, there could be up to n entries because I was tracking the longest power of each distinct substring. How would one need only n^2 space? $\endgroup$
    – pblpbl
    Commented Mar 28, 2020 at 21:29
  • $\begingroup$ @pblpbl, I already answered how. It's hard to comment on the specifics your approach since you haven't specified your algorithm. Perhaps you might like to edit the question to describe your algorithm and your analysis of its running time and space usage. $\endgroup$
    – D.W. ♦
    Commented Mar 29, 2020 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.