本文主要是介绍Leetcode 1156. Swap For Longest Repeated Character Substring [Python],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
交换一个字母,组成最长重复Substring。如果把字母按照重复段拆开成多个Substring(aaabbccaa--> aaa,bb,cc,aa),以每个Substring为对象思考,则最长的Substring就是其后(或前)增加一个相同的字母,并从中找最长的。但是每个字母在原String中的数量有限,所以用Counter记录这个上限,在对每个Substring的添加一个相同字母的时候不可超过这个上限。另外,如aaabaaaca,aaabaaa这样形式的,两个相同字母的Substriing被一个字母隔开,则可以尝试用外部字母和中间字母交换,如aaabaaaca的最后一个a和b交换。如果么有外部的相同字母,则只能把中间字母和两头的Substring的字母交换。同样也可以用Counter来做限制,看是否有其他相同与两端Substring的字母。
class Solution:def maxRepOpt1(self, text: str) -> int:char_Counter = collections.Counter(text)repeating = []i = 0while i < len(text) :curchar = text[i]cunt = 1while i+1 < len(text) and text[i+1] == text[i]:cunt += 1i += 1repeating.append((curchar, cunt))i += 1res = float('-inf')for char_and_num in repeating:curchar, number = char_and_num[0], char_and_num[1]res = max(res, min(number+1, char_Counter[curchar])) #Switch one letter to follow a repeating group, obtain the longest substringfor i in range(1, len(repeating)-1):prevchar = repeating[i-1][0]prevchar_num = repeating[i-1][1]nextchar = repeating[i+1][0]nextchar_num = repeating[i+1][1]curchar = repeating[i][0]curchar_num = repeating[i][1]if prevchar == nextchar and curchar_num == 1:#if two same char repeating group are with the same char, and be devided by only one different letter, try to switch the middle char to form the longest repeating substring from the outside char or the char within the repeating groups. res = max(res, min(prevchar_num+nextchar_num+1, char_Counter[nextchar]))return res
这篇关于Leetcode 1156. Swap For Longest Repeated Character Substring [Python]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!