[leetcode] 1156. Swap For Longest Repeated Character Substring

[leetcode] 1156. Swap For Longest Repeated Character Substring

Description

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"Output: 3Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:

Input: text = "aaabaaa"Output: 6Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:

Input: text = "aaabbaaa"Output: 4

Example 4:

Input: text = "aaaaa"Output: 5Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:

Input: text = "abcdef"Output: 1

Constraints:

1 <= text.length <= 20000text consist of lowercase English characters only.

分析

题目的意思是：给定一个字符串，交换其中的两个字母，使得字符串连续重复字符数最长。这道题我看了一下思路，首先用group记录一下每个字符的频率，例如 S = “AAABBCB” group为， [[A,3],[B,2],[C,1],[B,1]],然后d记录每个字符的总数，{A:3,B:3,C:1}, 然后最长重复字符有两种情况，第一种情况是group[i][ch]+1，即交换一个字符过来，交换过来的字符不一定与该ch字符相等，所以这时候d字典就是来限制的哈；另一种是两个相等的字符串之间只有一个其他字符串，然后把它交换到其他位置就可以了，当然交换来的字符串不一定是与现在的连续字符一样，所以这时候也是d来做限制哈。所以公式为：

res=max(res,min(cnt+1,d[k]))res=max(res,min(group[i-1][1]+group[i+1][1]+1,d[k]))

两个循环就能把这两种情况都包括在内了哈，当然我也没做出来，只是分析一下，哈哈哈

代码

class Solution: def maxRepOpt1(self, text: str) -> int: group = [] i=0 n=len(text) d={} while(i

参考文献

​​[LeetCode] Python 3, HashTable, O(n)​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。