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?

  • 1
    $\begingroup$ What do you mean by consecutive string? Do you mean a (nontrivial) power? $\endgroup$ – Yuval Filmus Mar 28 '20 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 Mar 28 '20 at 21:22
  • $\begingroup$ The English term is power. $\endgroup$ – Yuval Filmus Mar 28 '20 at 21:23

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.

  • $\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 Mar 28 '20 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. Mar 29 '20 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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