Skip to content

1316. Distinct Echo Substrings

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int distinctEchoSubstrings(string text) {
    unordered_set<string> seen;

    for (int k = 1; k <= text.length() / 2; ++k) {  // the target length
      int same = 0;
      for (int l = 0, r = k; r < text.length(); ++l, ++r) {
        if (text[l] == text[r])
          ++same;
        else
          same = 0;
        if (same == k) {
          seen.insert(text.substr(l - k + 1, k));
          // Move the window thus leaving a letter behind, so we need to
          // decrease the counter.
          --same;
        }
      }
    }

    return seen.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int distinctEchoSubstrings(String text) {
    Set<String> seen = new HashSet<>();

    for (int k = 1; k <= text.length() / 2; ++k) { // the target length
      int same = 0;
      for (int l = 0, r = k; r < text.length(); ++l, ++r) {
        if (text.charAt(l) == text.charAt(r))
          ++same;
        else
          same = 0;
        if (same == k) {
          seen.add(text.substring(l - k + 1, l + 1));
          // Move the window thus leaving a letter behind, so we need to
          // decrease the counter.
          --same;
        }
      }
    }

    return seen.size();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def distinctEchoSubstrings(self, text: str) -> int:
    seen = set()

    for k in range(1, len(text) // 2 + 1):  # the target length
      same = 0
      l = 0
      for r in range(k, len(text)):
        if text[l] == text[r]:
          same += 1
        else:
          same = 0
        if same == k:
          seen.add(text[l - k + 1:l + 1])
          # Move the window thus leaving a letter behind, so we need to
          # decrease the counter.
          same -= 1
        l += 1

    return len(seen)