Press "Enter" to skip to content

Posts tagged as “hashset”

花花酱 LeetCode 1316. Distinct Echo Substrings

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself.

Example 1:

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".


  • 1 <= text.length <= 2000
  • text has only lowercase English letters.

Solution 1: Brute Force + HashSet

Try all possible substrings

Time complexity: O(n^3)
Space complexity: O(n^2)


花花酱 LeetCode 820. Short Encoding of Words


Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?


Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].


  1. 1 <= words.length <= 2000.
  2. 1 <= words[i].length <= 7.
  3. Each word has only lowercase letters.


Remove all the words that are suffix of other words.


Time complexity: O(n*l^2)

Space complexity: O(n*l)