Решение задачи HackerRank "Repeat String"

19. Подсчитать количество `a` в бесконечно повторяющейся строке

Условие задачи:
Дана непустая строка s, состоящая из строчных английских букв. Строка повторяется бесконечно.

Также дано число n.

Необходимо определить, сколько символов 'a' содержится в первых n символах бесконечно повторяющейся строки.

Пример 1:

s = "abcac"
n = 10

Бесконечная строка:
abcacabcacabcac...

Первые 10 символов:
abcacabcac

Результат: 4

Пример 2:

s = "a"
n = 1000000000000

Результат: 1000000000000

Спойлеры к решению

Подсказки

💡 Не нужно создавать строку длиной n.
💡 Сначала посчитай количество 'a' в одном экземпляре строки s.
💡 Количество полных повторений строки равно n / s.length().
💡 После полных повторений может остаться префикс длиной n % s.length().
💡 Для n и результата используй long.

Решение

public static long repeatedString(String s, long n) {
    long countInString = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == 'a') {
            countInString++;
        }
    }

    long fullRepeats = n / s.length();
    long result = fullRepeats * countInString;

    int remainder = (int) (n % s.length());

    for (int i = 0; i < remainder; i++) {
        if (s.charAt(i) == 'a') {
            result++;
        }
    }

    return result;
}

Сначала считаем количество символов 'a' в одной строке:

for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == 'a') {
        countInString++;
    }
}

Количество полных повторений:

long fullRepeats = n / s.length();

Например, если:

s.length() = 5
n = 12

то строка полностью помещается два раза, а ещё остаются два символа:

12 / 5 = 2
12 % 5 = 2

Количество 'a' в полных повторениях:

long result = fullRepeats * countInString;

После этого отдельно проверяется оставшийся префикс:

int remainder = (int) (n % s.length());

for (int i = 0; i < remainder; i++) {
    if (s.charAt(i) == 'a') {
        result++;
    }
}

Такой подход не создаёт строку огромного размера и работает даже для очень больших значений n.

Временная сложность — O(|s|), дополнительная память — O(1).