Сложность: easy
Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.
Пример:
Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.
👨💻 Алгоритм:
1⃣Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву.
2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.
3⃣После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total.
😎 Решение:
class Solution:
def countLetters(self, S: str) -> int:
total = 0
left = 0
for right in range(len(S) + 1):
if right == len(S) or S[left] != S[right]:
len_substring = right - left
total += (1 + len_substring) * len_substring // 2
left = right
return total
Ставь 👍 и забирай 📚 Базу знаний