← К задачам Режим собеседования 20:00
Обычный режим ← Предыдущая Следующая →

5123. Количество бинарных подстрок

Easy 1 решил
Дана строка s, состоящая только из символов '0' и '1'. Посчитайте число непустых подстрок, для которых выполняются оба условия:
1. количество нулей равно количеству единиц;
2. все нули идут одним куском подряд, и все единицы — одним куском подряд (то есть подстрока имеет вид 0…01…1 или 1…10…0, без чередования внутри).

Считаются вхождения по позициям: одинаковые по тексту куски в разных местах строки — это разные подстроки и учитываются отдельно.

Примеры подходящих подстрок: 01, 10, 0011, 1100. Не подходит, например, 0101 (больше двух групп) или 001 (нулей и единиц разное число).

s = "00110011"
индексы: 0 1 2 3 4 5 6 7
         0 0 1 1 0 0 1 1

Подходящие вхождения (всего 6):
  [0:4] 0011
  [1:3] 01
  [2:6] 1100
  [3:5] 10
  [4:8] 0011   ← тот же текст, что [0:4], но другое место
  [5:7] 01     ← то же для [1:3]

Ответ: 6

Примеры:

Вход: 00110011
Выход: 6
Объяснение: Шесть вхождений по индексам: [0:4] 0011, [1:3] 01, [2:6] 1100, [3:5] 10, [4:8] 0011, [5:7] 01. Два раза встречается текст «0011» и два раза «01» — это разные места строки, поэтому каждое считается отдельно.
Вход: 10101
Выход: 4
Объяснение: Четыре подходящие подстроки по индексам: [0:2] «10», [1:3] «01», [2:4] «10», [3:5] «01». Каждая — соседняя пара символов 1 и 0 (или 0 и 1); всего 4.
Вход: 0011
Выход: 2
Объяснение: Группы [2,2]: можно взять 0011 целиком и внутренний 01. Ответ min(2,2)=2.
Вход: 000111
Выход: 3
Объяснение: Группы [3,3]: подстроки 000111, 0011 (срез по краям) и 01 — ровно min(3,3)=3.
Вход: 0
Выход: 0
Объяснение: Одна группа без соседней другой — подходящих подстрок нет.

Ограничения:

1 <= s.length <= 10^5 s состоит только из символов '0' и '1'

Теги:

Строки

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!