The fastest way to calculate all the substrings of a string and check it for a given condition

Question

What is the fastest way to calculate all possible substrings of a given string and check them for the following condition.

Condition: If the first and last character of the generated substring are the same, then the count is increased by one. We need to find all such possible substrings of a given very large string.

I tried the naive brute force approach, but it did not work for strings with a length of 10 ^ 7. Please help :(

for(int c = 0 ; c < length ; c++ ) { for( i = 3 ; i <= length - c ; i++ ) { String sub = str.substring(c, c+i); System.out.println(sub); if(sub.charAt(0) == sub.charAt(sub.length()-1)){ count++; } } } 

Answer 1

Your current solution is quadratic to the size of the input string or O (n ^ 2)

You can solve this more efficiently by counting the appearance of each character in the string and then counting the number of substrings that can be created with that character.

eg. if the character occurs 4 times, then this leads to 3 + 2 + 1 = 6 substrings.

To do this, you can use the following formula: ((n-1) * n) / 2

Thus, the complexity of the algorithm comes down to O (n), because to count each character you only need to cross the line once.

I believe this code should work:

 public static void main(String[] args) { String str = "xyzxyzxyzxyz"; Map<Character, Integer> map = new HashMap<>(); for (char c : str.toCharArray()) { Integer count = map.get(c); if (count == null) count = 0; map.put(c, count + 1); } int sum = 0; for (int n : map.values()) sum += ((n - 1) * n) / 2; System.out.println(sum); }