Подсчитайте подпоследовательности длины 4, делящиеся на 9

Подсчитать подпоследовательности длины 4 строки длины n, которые делятся на 9.

Например, если входная строка 9999 тогда cnt=1

Мой подход похож на Brute Force и требует O (n^3 ). Есть ли лучший подход, чем этот?