Counting occurrences of “hi” in a string, except where followed by “x”

Question

I already solved this one from CodingBat, but I'm unsatisfied with my solution and I feel I could have made it much shorter. Most of the other recursion tasks could be solved by a one line conditional for the base case and a one line return statement usually using ternary operator. So, could I have made this any shorter or more readable?

Given a string, compute recursively the number of times lowercase "hi" appears in the string, however do not count "hi" that have an 'x' immedately before them.

public int countHi2(String str) {
  if (str.length() <= 1) {
    return 0;
  }


  if (str.startsWith("x") && str.charAt(1) != 'x') {
    return countHi2(str.substring(2));
  }
  else if (str.startsWith("hi")) {
    return 1 + countHi2(str.substring(2));
    }
  else {
    return countHi2(str.substring(1));
  }
}

Answer 1

It doesn't get much shorter than that. But some other improvements are possible.

The current algorithm uses startswith method to check for x and hi, and as such it advances by 1 or 2 characters at a time. This is inefficient.

Another performance issue is creating many temporary strings in the process (because of substring).

It would be better to use indexOf instead of startswith, which will allow you to jump multiple characters at a time. Another big improvement would be to avoid temporary string generation, by creating a helper function that tracks the position to check. Something like this:

public int countHi2(String str) {
    return countHi2(str, 0);
}

public int countHi2(String str, int start) {
    start = str.indexOf("hi", start);
    if (start == -1) {
        return 0;
    }

    int count = 0;
    if (start == 0 || str.charAt(start - 1) != 'x') {
        count++;
    }
    return count + countHi2(str, start + 2);
}