class Solution { //using rabin karp rolling hash algo to replace text.substring ->O(n) to O(1) //which makes the whole algo O(n^2) private static final int PRIME = 101; private static final int MOD = 1_000_000_007; public int distinctEchoSubstrings(String text) { /* Q66 of dp playlist , echo substring(ess) */ int n = text.length(); // dp[i][j] : hash value of text[i:j] int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) { long hash = 0; for (int j = i; j < n; j++) { hash = hash * PRIME + (text.charAt(j) - 'a' + 1); hash %= MOD; dp[i][j] = (int) hash; } } //make a HS to store distinct echo substrings HashSet<Integer> set = new HashSet<>(); //checking all ess of length 2->n/2 for(int len = 1 ; len <= n/2 ; len++){ /* we keep checking characters at a gap of length and increasing count if chars are equal we keep the count going for potential ess ,if chars are not equal our current potential ess is ruined and we start checking again for new ess from count = 0 if count = len , we add the substring in the HS and count-- to check if the next characters are making and ess , basically it means deleting a character from behind and continue checking to find next ess */ int count = 0; for(int i = 0,j = len ;j < n ; i++ , j++){ char ch1 = text.charAt(i) , ch2 = text.charAt(j); if(ch1 == ch2) count ++; else count = 0; if(count == len){ //here instead of substring function we store a unique hashvalue for i to jth string in dp set.add(dp[i][j]); count --; } } } System.out.print(set); return set.size(); } }