1316. Distinct Echo Substrings

Description

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string).

 

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".

 

Constraints:

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

 

Solutions

Solution: Sliding Window

• Time complexity: O(n²)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {string} text
 * @return {number}
 */
const distinctEchoSubstrings = function (text) {
  const n = text.length;
  const distinctSubStr = new Set();

  for (let length = 1; length <= Math.floor(n / 2); length++) {
    let left = 0;
    let sameCount = 0;

    for (let index = length; index < n; index++) {
      const letter = text[index];

      sameCount = text[left] === letter ? sameCount + 1 : 0;
      left += 1;

      if (sameCount !== length) continue;
      const subStr = text.slice(index - length + 1, index + 1);

      distinctSubStr.add(subStr);
      sameCount -= 1;
    }
  }
  return distinctSubStr.size;
};