Python | LeetCode
Задача: 1422. Maximum Score After Splitting a String
Сложность: easy
Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).
Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.
Пример:
Input: s = "011101"
Output: 5
Explanation:
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5
left = "01" and right = "1101", score = 1 + 3 = 4
left = "011" and right = "101", score = 1 + 2 = 3
left = "0111" and right = "01", score = 1 + 1 = 2
left = "01110" and right = "1", score = 2 + 1 = 3
👨💻 Алгоритм:
1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения.
2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.
3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума.
😎 Решение:
class Solution:
def maxScore(self, s: str) -> int:
ones = s.count('1')
zeros = ans = 0
for i in range(len(s) - 1):
if s[i] == '1':
ones -= 1
else:
zeros += 1
ans = max(ans, zeros + ones)
return ans
Ставь 👍 и забирай 📚 Базу знаний
5 · 633 ·