给你一个由N个字母“a”和/或“b”组成的字符串S在一次移动中,您可以用一个字母替换另一个字母(“A”替换“B”或“B”替换“A”)。
编写一个函数解决方案,给定这样一个字符串S,返回获取不包含三个相同连续字母实例的字符串所需的最小移动次数。
示例:
给定s=“baaaa”,函数应返回1。移动中没有三个相同的连续字母的字符串是“baaba”
给定s=“baaabbba”,函数应返回2。有四个有效字符串可以在两个移动中获得:例如,“bbaabbaabbaa”
给定s=“baabab”,函数应返回0
为以下假设编写一个有效的算法:
N是范围[0…200000]内的整数
字符串s仅由字符“a”和/或“b”组成
下面是我的解决方案,但只有14%的可变性需要有人帮我做算法
def solution(A):
if len(A) == 0:
return None
prev_char = ''
move = 0
for current in A:
if prev_char == current:
count += 1
if count == 3:
move += 1
else:
count = 1
prev_char = current
return move
最佳答案
也许这能行首先用相邻的相同字母将输入分成若干段。接下来,修复每个段的移动次数是可以在其长度中容纳3次的次数。
from itertools import groupby
def solution(A):
splitted = [''.join(g) for _, g in groupby(A)]
moves = 0
for segment in splitted:
moves += int(len(segment) / 3)
return moves
关于python - 返回三个相同连续字母的最小移动次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57903176/