Может стоит попробовать certificate — based authentication? Он конечно не исключит возможность кражи ключа из андроид приложения, но усложнит задачу на порядок.
Как вариант можно посчитать хэши подстрок нужной длины, после этого отсортировать их. Еще за один проход мы найдем максимальное число повторений одного хэша, еще за один проход в строке найдем исходную подстроку(хотя можно сразу же хранить).
