25. Подсчитать количество символов в повторяющейся строке
Условие задачи:
🔥 Дана строка s, состоящая из строчных английских букв, которая повторяется бесконечно.
Дано целое число n. Нужно определить, сколько букв 'a' содержится в первых n символах этой бесконечной строки.
📌 Пример 1:
Вход: s = "abcac", n = 10
Выход: 4
Пояснение:
Бесконечная строка: "abcacabcacabcac..."
Первые 10 символов: "abcacabcac"
Количество 'a' = 4
📌 Пример 2:
Вход: s = "a", n = 1000000000000
Выход: 1000000000000
Спойлеры к решению
Подсказки
💡 Не создавайте строку длиной
💡 Найдите количество полных повторений строки:
💡 Подсчитайте количество
💡 Умножьте на количество полных повторений.
💡 Обработайте остаток
💡 Используйте тип
n — это приведёт к переполнению памяти.💡 Найдите количество полных повторений строки:
n / s.length().💡 Подсчитайте количество
'a' в одной строке s.💡 Умножьте на количество полных повторений.
💡 Обработайте остаток
n % s.length().💡 Используйте тип
long.Решение
class Result {
public static long repeatedString(String s, long n) {
long countAInOneString = 0;
// считаем количество 'a' в одной строке
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'a') {
countAInOneString++;
}
}
long fullRepeats = n / s.length();
long totalCount = fullRepeats * countAInOneString;
long remainder = n % s.length();
// считаем 'a' в остатке
for (int i = 0; i < remainder; i++) {
if (s.charAt(i) == 'a') {
totalCount++;
}
}
return totalCount;
}
}
📌 Что важно помнить:
✅ Временная сложность — O(|s|)
✅ Память — O(1)
✅ Мы не создаём огромную строку
✅ Обязательно используем long
✅ Решение проходит большие тесты HackerRank