您在std库中拥有大部分工具。

• 总是尽你所能去做最长的延伸。那与其说是"算法"，不如说是"逻辑问题分析"。s.split(".").
• 然后转换为数字：列表解析上的len
• 你可以去只要预算〉1得心应手：while
• 你可以修理一个完整的坑洞，也可以比你的预算少1个。方便：min.
• 在每个通道上固定坑洞。方便：作为最后一个参数的1是替换的数目-即，你用4的预算支出修复一个3孔凹坑，而不是所有3孔凹坑。

以下是我的看法：

def budget(s : str, b :int):

    fixed = 0
    #while you have a budget
    while b >1:
        #split on `.`, sorted by longest length, remove zero, lengths.
        li = s.split(".")
        li2 = sorted([len_ for v in li if (len_:=len(v))],reverse=True)

        #is there anything to fix?
        if li2:
            #fix what you can...
            fix = min(b-1, li2[0])
            # pay for it and total up what you've done
            b -= (fix+1)
            fixed += fix
            #now, replace the potholes for the next pass
            s = s.replace("x"*fix,"."*fix, 1)
        else:
            break

    return fixed
        

def test():

    dataexp = [
        (dict(s="...xxx..x....xxx.",b=7),5),
        (dict(s="xxxx",b=19),4),
        (dict(s=".x.",b=19),1),
        (dict(s=".x.",b=1),0),
        (dict(s=".xxx.",b=2),1),
        ]

    for inp, exp in dataexp:
            got = budget(**inp)
            msg = f"\nbudget for {str(inp):100.100} \nexp :{exp}:\ngot :{got}:\n"
            if exp == got:
                print(f"✅! {msg}")
            else:
                print(f"❌!  {msg}")

test()

输出：

✅! 
budget for {'s': '...xxx..x....xxx.', 'b': 7}                                                                   
exp :5:
got :5:

✅! 
budget for {'s': 'xxxx', 'b': 19}                                                                               
exp :4:
got :4:

✅! 
budget for {'s': '.x.', 'b': 19}                                                                                
exp :1:
got :1:

✅! 
budget for {'s': '.x.', 'b': 1}                                                                                 
exp :0:
got :0:

✅! 
budget for {'s': '.xxx.', 'b': 2}                                                                               
exp :1:
got :1:

你也许可以递归地做这件事，不确定。最近听了一本关于Python/JS递归的书的作者的播客，他说大多数时候循环的工作效果和递归减去退出条件并发症一样好，我觉得我对大多数递归的事情一无所知是正确的（除了在树状分支问题中递归是 * nice *）。
p.s.我突然想到你不是被要求 * 修正 *，只是 * 预算 *。所以split只需要出现一次，在循环之上。然后你可以使用类似pots = li2.pop()的东西来挑选下一个块，在循环中。你不需要replace。其余的或多或少保持相等。

数一数。
在您的示例问题中，它将是3-〉2，1-〉7，2-〉2
按降序维护它们。使用一种树Map或一个最大堆，以频率作为每个块的长度值作为键。
这可以在一次通过中完成，并且具有nlog（n）的复杂度
然后从堆中取出每个元素，看看它是否符合预算。
在本例中，第一个要素是值为2的关键字3。您最多可以容纳多少个要素？您可以用预算4取出前3个要素，然后从后3个要素中取出2个要素，因为您的预算剩余仅为3。您可以确定的总数为3 + 2 = 5。