1156 Swap For Longest Repeated Character Substring

Posted on

1156. Swap For Longest Repeated Character Substring

1
2
3
4
5
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.
Input: text = "aaabaaa"
Output: 6
Input: text = "aaabbaaa"
Output: 4

可以分为两种情况，

  1. 两边相同的字符被中间一个字符隔开，
  2. 连续最长的Substring，从别处swap到边上。

对于最长的char已经用完，在其余位置没有的情况，每次取值的时候，用

1
2
rs=max(rs,min(left+right+1,count[char]),
rs=max(rs,min(LongSubstring+1,count[char]))

来避免。

这道题在提交的过程中，如果用List来存放相同char的index，在之后的遍历过程中，用了多次list.get(i) 和 list.get(i-1) 来判断是否是连续的还是间隔了一个字符，如果list是LinkedList， 5.01%，494ms, 如果是ArrayList，则是51%，7ms, 很好理解，但是没想到会差距这么大，估计test case 中的string 很长，重复的有很多，导致每次get(i)都 O(n), 之后在做题的时候要注意这些细节。