Non-negative Integers without Consecutive Ones

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

Input: 5
Output: 5
Explanation: 
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

Note: 1 <= n <= 109

public class Solution {
    public int findIntegers(int num) {
        StringBuilder sb = new StringBuilder(Integer.toBinaryString(num)).reverse();
        int n = sb.length();
        // a[i] means length of i and ends with 0.
        // b[i] means length of i and ends with 1.
        int a[] = new int[n];
        int b[] = new int[n];
        a[0] = b[0] = 1;
        for (int i = 1; i < n; i++) {
            a[i] = a[i - 1] + b[i - 1];
            b[i] = a[i - 1];
        }
        // all possible strings of length n with no consecutive ones
        int result = a[n - 1] + b[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            // if we encounter a 11 that is not possible in any of our solutions , that
            // means we dont need to substract anything and everything in result is < num
            if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1')
                break;
            // If we encounter a 00 that means we need to reduce those counts ending with 1s
            // because they will be > num
            if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0')
                result -= b[i];
        }

        return result;
    }
}