Find the number of all specific substrings in a string

Question

I would like to ask a code review regarding a concrete exercise. Let's suppose I have to get the number of all specific substrings in a string.

We call something specific if any of these conditions are is true:

• The string consists of similar characters. For example: "aaaaa"

• The string consists of similar characters except the middle one, which can be anything. For example: "aabaa"

To do this, I first decided to get all combinations into a list. I did it in an O(n3) solution just with 2 basic for loops and using substring() (see more), this way:

private static List<String> allCombinations(String s) {
 List<String> output = new ArrayList<>();
 for (int i = 1; i <= s.length(); i++) {
 for (int j = 0; j <= s.length() - i; j++) {
 output.add(s.substring(j, j + i));
 }
 }
 return output;
}

Subsequently, I used this method to count how many of these are special:

static long substrCount(String s) {
 long res = 0L;
 List<String> output = allCombinations(s);
 for (String x : output) {
 if(isSpecial(x)){
 res++;
 }
 }
 return res;
}

isSpecial() looks like this:

private static boolean isSpecial(String input) {
 Set<Character> occurrences = new HashSet<>();
 for (int i = 0; i < input.length(); i++) {
 occurrences.add(input.charAt(i));
 }
 if (occurrences.size() > 2) {
 return false;
 }
 if (occurrences.size() == 1) {
 return true;
 }
 return input.length() % 2 == 1 && input.charAt(0) == input.charAt(input.length() - 1) && input.charAt(input.length() / 2) != input.charAt(0);
}

I've got 2 questions:

1. This is a practice exercise with provided tests, and most of the test cases failed due to time complexity problems. How could I reduce the time complexity of my solution?

2. If you could give me any general feedback what to improve in - based on my code - I would be really thankful.

Thank you in advance.

Answer 1

First off, I believe you are confusing the terms "specific" and "special" in the description.

Method isSpecial

• You could move the if (occurrences.size() > 2) statement into the for loop, because once you know that there are more than 2 different characters, there is no need to continue adding more characters to the Set. Then you can also initialize the HashSet to an initial size of 3, because it never can grow larger than that.

• You don't need the part input.charAt(0) == input.charAt(input.length() - 1) in the final expression, because when the length is more than two and if there are exactly two different characters, it can never be false when input.charAt(input.length() / 2) != input.charAt(0) is true.

• Finally I'd put input.length into a local variable. That will speed up the for loop by a tiny amount by avoiding the method call and it will make the final expression a bit shorter and thus better to read

private static boolean isSpecial(String input) {
 int len = input.length();
 Set<Character> occurrences = new HashSet<>(3);
 for (int i = 0; i < len; i++) {
 occurrences.add(input.charAt(i));
 if (occurrences.size() > 2) {
 return false;
 }
 }
 if (occurrences.size() == 1) {
 return true;
 }
 return len % 2 == 1 && input.charAt(len / 2) != input.charAt(0);
}

Method substrCount

This method can be shorten significantly by using Java 8's Stream API:

static long substrCount(String s) {
 return allCombinations(s).stream().filter(ClassName::isSpecial).count();
}

(ClassName is the name of the class isSpecialis in.)