Scale Engineer

Distinct Echo Substrings

Hard
#1225Time: O(n^3). There are two nested loops, giving O(n^2) combinations of starting positions `i` and half-lengths `len`. Inside the inner loop, creating and comparing substrings of length `len` takes O(len) time. The total complexity is roughly the sum of `len` over all iterations, which amounts to O(n^3).Space: O(n^2). The `HashSet` can store up to O(n^2) distinct substrings. The total length of all distinct substrings stored in the set is also bounded by O(n^2).
Patterns
Rolling HashHash Function
Data structures
StringTrie

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward brute-force approach that systematically checks every possible substring that could be an echo substring. It iterates through all possible starting positions and lengths, and for each candidate, it performs a direct string comparison to verify if it's an echo substring. A HashSet is used to count only the distinct ones.

Algorithm

  • Initialize an empty HashSet<String> to store the unique echo substrings found.
  • Iterate through every possible starting position i from 0 to n-1, where n is the length of the text.
  • For each starting position i, iterate through every possible length len for the first half of a potential echo substring. The loop for len runs as long as the full substring of length 2 * len is within the bounds of the text (i.e., i + 2 * len <= n).
  • Inside the loops, extract the two adjacent substrings of length len: first_half = text.substring(i, i + len) and second_half = text.substring(i + len, i + 2 * len).
  • Compare first_half and second_half. If they are identical, it means we've found an echo substring.
  • Add the full echo substring text.substring(i, i + 2 * len) to the HashSet. The set automatically handles duplicates.
  • After all iterations, the size of the HashSet is the number of distinct echo substrings.

Walkthrough

The core idea is to generate and test all potential echo substrings. An echo substring must have an even length, say 2 * len. It is formed by concatenating a string a of length len with itself. We can iterate through all possible starting positions i and all possible half-lengths len. For each pair of (i, len), we check if the substring of length len starting at i is equal to the substring of length len starting at i + len. If they are equal, we have found a valid echo substring, which we add to a HashSet to ensure that our final count is of distinct substrings.

import java.util.HashSet;import java.util.Set; class Solution {    public int distinctEchoSubstrings(String text) {        int n = text.length();        Set<String> found = new HashSet<>();                // i is the starting index of the potential echo substring        for (int i = 0; i < n; i++) {            // len is the length of the first half 'a'            // The full substring has length 2 * len            for (int len = 1; i + 2 * len <= n; len++) {                String s1 = text.substring(i, i + len);                String s2 = text.substring(i + len, i + 2 * len);                                if (s1.equals(s2)) {                    // Found an echo substring. Add the full string 'a+a' to the set.                    // Note: Adding just 's1' would also work and be slightly more memory efficient,                    // as a1+a1 == a2+a2 if and only if a1 == a2.                    found.add(text.substring(i, i + 2 * len));                }            }        }                return found.size();    }}

Complexity

Time

O(n^3). There are two nested loops, giving O(n^2) combinations of starting positions `i` and half-lengths `len`. Inside the inner loop, creating and comparing substrings of length `len` takes O(len) time. The total complexity is roughly the sum of `len` over all iterations, which amounts to O(n^3).

Space

O(n^2). The `HashSet` can store up to O(n^2) distinct substrings. The total length of all distinct substrings stored in the set is also bounded by O(n^2).

Trade-offs

Pros

  • The logic is simple and easy to understand and implement.

Cons

  • The time complexity of O(n^3) is too slow for the given constraints (n <= 2000) and will likely result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution { private long [] h ; private long [] p ; public int distinctEchoSubstrings ( String text ) { int n = text . length (); int base = 131 ; h = new long [ n + 10 ]; p = new long [ n + 10 ]; p [ 0 ] = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int t = text . charAt ( i ) - 'a' + 1 ; h [ i + 1 ] = h [ i ] * base + t ; p [ i + 1 ] = p [ i ] * base ; } Set < Long > vis = new HashSet <>(); for ( int i = 0 ; i < n - 1 ; ++ i ) { for ( int j = i + 1 ; j < n ; j += 2 ) { int k = ( i + j ) >> 1 ; long a = get ( i + 1 , k + 1 ); long b = get ( k + 2 , j + 1 ); if ( a == b ) { vis . add ( a ); } } } return vis . size (); } private long get ( int i , int j ) { return h [ j ] - h [ i - 1 ] * p [ j - i + 1 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem